Albert Gore Jr. Joseph Lieberman Democratic 4,113,791 60.22%
George W. Bush Richard Cheney Republican 2,405,676 35.22%
Hillary Rodham Clinton Democratic 3,747,310 55.27%
Rick Lazio Republican 2,915,730 43.01%
Mind that Rick Lazio was considered to be a bit more moderate and less "southern" than Bush was and many New Yorkers considered Clinton's run to be blatant carpetbagging/nepotism of some order (hey vote for me I am the President's wife). Meanwhile, Gore ran the campaign of an admittedly boring technocrat who made trendy liberal issues like gun control and global warming focus points of his campaign and his opponent was widely seen as a hillbilly frat boy by many.
If this comparison proves anything it is that Clinton did pretty well considering she had a bigger challenge (at least in New York state). And also that she did not run 15 points behind Gore.
EDIT: I see what you did there.