Here's the thing, though: he's a criminal. Paying a prostitute for sex is an actual-factual crime, isn't it?
I felt differently about Clinton/Lewinsky because that was just old-fashioned adultery and nobody's business IMO. I didn't LIKE it or admire him for it, but it didn't seem relevant to his service in the way that this is. I don't think it's a good policy to allow our elected officials to get away with criminal activity, whether vice crimes or otherwise. Like it or not, when you're in a position of power you're expected to adhere yourself to the laws you enforce/enact for others.