Another vote for Kefka (FFIII)–you’ve got to admire a villain who enjoys his work that much.
Second place should go to Magus (CT), if only because he has the greatest henchman any villain has ever had–Ozzie, Slash, and Flea. 
Saavedro from Myst 3. Love the little speech he gives when you solve the elevator puzzle and enter the room that he links out of.
Definately, LeChuck in the first three games was great.
First he was a ghost pirate, then he was ressurrected as a zombie pirate, then exposure to highly volatile voodoo magic transformed him into a demon pirate.
Sadly his fourth incarnation, in which he had the ability to freely morph between all of his previous incarnations, sucked balls.
They didn’t work for him, they were his friends.
Also, the best villain I’ve seen in any videogame is Sephiroth from Final Fantasy VII. Not only because he’s all bad and mean and tragic and whatnot, but also because he’s so damn good-looking and cool. Long gray hair, black clothes, really long sword all equal to great coolness.
How about ‘the administrator’ from Half-Life? You never get to fight him (and if you take some pot shots, your bullets just make sparks, like he’s made of metal.)
Oh, and in the end, he wins. Okay, maybe it’s a tie in Half-Life, but he definitely wins in Opposing Force.
There’s that, too 
A beautiful villain makes it more interesting – hard to have sympathy for some slime-dripping beasty from the nine hells.
In the end he looks positively angelic. Desperate. Tragic. And that music, too…
My favorite villain? David Bowie, the second level boss in Amplitude.
Just for sheer creepiness…Pyramid head from Silent Hill 2 or the Queen from Ico
Actually, I’ll say his Monkey Island 3 incarnation wasn’t that great. “Get me more SLAW!”, not the best catch phrase ever.
But LeChuck in 1 and 2 were right on.
The Cyberdemon from Doom 2. That was one scary looking mofo.
Freakin ghosts from Pac-Man…
Krelian from Xenogears.
He has a believable development,he isn’t crazy or spiteful.
He coldly manipulates everyone to get what he wants,and in the end when he has it he says bye to the heros,adding that he envies them.
He struck me as much more interesting than a laughing maniac or uber-powerful god.
Goombas
Shodan from the original System Shock, not the sequel–she was just a bit too damn goofy in SS2, plus she was diluted too much by The Many, and by the end of the game, taking care of her just felt like an impersonal task to accomplish. The realization that, more than any videogame villain before, I hated her was the bit of the first game, after creeping and running and fighting through several levels and mazes to what was supposed to be the station’s last cluster of survivors, and having that…er, just not work out in Mr. Hacker’s favor. So killing her at the end of the first 'Shock was personal, and highly satisfying.