Probably a very trivial answer from an American point of view, but from a European perspective this is rather strange. In Europe the private life of a president is in many cases, well, private. As long as he/she rules the country decently, there is no problem.
"decently" is in the eye of the beerholder. That's problem #1 with your statement. From the point of view of a large number of people (those who voted against him - roughly 1/2 the country), he did NOT rule the country "decently".
In politics, ANY reason to attack an opponent is a good reason. This one was just as good as anything else.
In addition, a political sex scandal is a very popular entertainment. People eat it up. It's sex, scandal, and politics all meshed together. Not to mention all the comedy material that arose out of this specific one. As exhibit, I present to you Anthony "flashing" Wiener.
As another answer noted, there used to be somewhat of an expectation that a President isn't a bald-faced liar. Especially after the last "I'm not a crook!" was forced from office over it. In this case, we had: adultery (including lying to your wife), coverup, lying to investigators in deposition, lying to a grand jury, AND lying to pretty much the entire country in a televised speech.
As far as it is described, the relationship was not "forced": the president did not abused his "power"... Thus this is a personal affair.
This is where you are 100% wrong (unless you're a closet libertarian :)
Americans have it drilled in their heads from the moment of entering job market, for the last 20 years, about sexual harassment and the evils of imposing your (typically male) sexual attention on a person who is in a power-imbalance relationship with you - including, and especially at, workplace.
There can't POSSIBLY EVER be a greater power imbalance than between President of the frigging United States of America ("the most powerful man in the world") and an intern in the federal government. That's a far as a power imbalance can possibly stretch.
Frankly, ANY OTHER male in that position, had he not been a Democratic politician, would have been crucified by feminists.
Any CEO or manager in a private company would immediately loose his job (among higher profile ones: Boeing CEO fell that way. Or look at the witch-hunt feminists started against Herman Cain the moment he became a political threat).
The fact that the relationship was consensual is 100% irrelevant to the power imbalance and thus sexual harassment
source #1: many many years of mandatory annual sexual harassment training).
Source #2: City/County of San Francisco government, publication "Sexual Harassment: Frequently Asked Questions by Ann Lehman & Hillary Flynn, Sexual Harassment Task Force May 1996 (Revised September 1998, August 2008)"
The reason for that is that the assumption of "there's no way to tell if the consent was caused by the power imbalance"
The part that causes the most problems from a European perspective is that Clinton lied about his encounters with Lewinsky. In Europe, this would probably created a climate of anti-trust.
The problem wasn't JUST that he lied (that was a problem but not a legal one). Although as you noted, that was definitely a problem in that it imposed a great(er) level of distrust in politicians from people.
The problem was that he lied under oath in a criminal deposition - and perjury is a criminal offense. Again, the only reason he's NOT in jail (like, say, Walter Libby on identical charge) is because he was a popular left wing politician in a period of good economy.