Black Mage, from 8-Bit Theater. I sympathize with his inability to win White Mage’s heart.
What, Kefka isn’t hot?
I thought Kefka was pretty hot…
I can’t for the life of me summon up the name of the Evil Guys right now, but the book is Once a Hero** (the first one that focuses on Esmay Suiza).
And I should qualify my fondness by stating that I’ve read every book Moon’s written and generally love every single aspect of every single book.
I second (or is it third?) Rickman’s character in Die Hard – the first recent villain who was scary because he was smart, as opposed to being big, sadistic and/or handy with a firearm.
This concept reached its apogee with Hopkins’ Lector, the gold standard of absolutely evil characters that you can’t not admire. (If you haven’t seen the movie Hannibal, please don’t – read the book instead, you’ll thank me).
I wouldn’t exactly call him a villain. He’s a bastard. He’s annoying as all-get-out. But he’s also sort of not-evil. I mean, he risks an awful lot to save the world. Maybe he doesn’t really care about people (aside from finding them quite funny) but he’s done a few decent things in his life and at least feels like keeping the whole world around. He’s not really a villain, though he’s not exactly what I’d cal a good-guy.
Then again, I’m not sure Lina qualifies, either. 
I offer the exact opposite advice, but I do love that character.
Bill the Butcher from Gangs of New York.
Leonardo Leonardo from Clerks: The Series.
Al Pacino in The Devil’s Advocate…and the Godfather Part 2.
that’s such a great book - very readable space opera series in fact.
(I like almost every book, ever read the short story collection she’s got out?)
[/hijack]
Edward Hyde in League of Extraordinary Gentlemen.
Like with the OP’s nomination of Kefka, there’s something really enjoyable about an evil man who so wholeheartedl enjoys it.
(Although there’s also something enjoyable about one who justifies it and thinks he’s doing, good, but I really like Hyde’s unrestrained savagery.)
Plus… (Spoilers for the end of volume 2)
[spoiler]His rape and murder of Griffin was a sort of utterly twisted poetic justice.
And charging a Martian Tripod…alone…and unarmed…AND WINNING the fight? That’s badassitude right there.[/spoiler]
No one’s mentioned Flashman yet ?
I’d say skip both and go rent Silence of the Lambs again…
As to the OP, I offer David Bowie in Labyrinth. Oooh, 80s hair!
The Bloodhorde? The Beningty of the Compassionate Hand? The um… large prey hunters? The New Texas Godfearing Militia?
My favourite: Lucius Cornelius Sulla as he’s described in McCullough’s “First man in Rome” series. Cruel, ice cold, ruthless, doesn’t hesitate to murder people who are close to him if they are more useful to him dead than alive - but somehow still likeable.
Dang, you stole mine. I loaned my books out to a few people and everyone else just thought he was horrible.
My #1 would also be Alan Rickman as Hans Gruber in Die Hard. Possibly my favorite movie villain of all time.
Samuel L. Jackson as Jules Winfield in Pulp Fiction (a hitman, but so cool and funny, and ultimately redeemed himself in the end).
Johnny Depp as Agent Sands in Once Upon A Time In Mexico (“This puerco pibil is the finest I’ve ever had. It is so good that I will finish my meal, go into the kitchen, and shoot the cook. Because that’s what I do. I restore balance to this country.” And then he does.)
Christopher Walken in Suicide Kings. A notorious gangster that a bunch of prep school friends kidnap and ransom, we like him a lot more than any of them. How can you not like Walken, even when he’s in super-creepy mode?
From comics, Tao from Sleeper is one of the ultimate evil scheming bastards, the kind of guy even Batman might not be able to beat with prep time. But he is charming (in a “silver-tongued devil” sort of way), and his plans to throw the world into chaos for his own amusement almost seem preferable to the conformist worldview of his arch-enemy John Lynch.
Miss Misery from Sleeper is another likeable villain. This femme fatale will become deathly ill and wither away if she doesn’t do horrible things (often to undeserving victims). So she is violent, devious, and manipulative as a means of personal survival, and just happens to be dead sexy too.
Since I’ve had a huge crush on Michael Easton since he played Tanner Scofield on “Days of our Lives,” I have to add the vampire Caleb from “General Hospital.” Nobody played a vampire better, and the man is freaking gorgeous.
And I think that the above is why I like him so much.
I also second Einmon. Watch Silence of the Lambs. Hell, read Silence. But avoid Hannibal in either printed or cinematic form.
Also, Ben Kingsley in Sneakers. Again, smart makes for a much better villain than physically imposing.
KHAAAAAAAAAAAAN!
(I can’t believe I’m the first to say that. )
Just gotta 3rd? 4th? 10th? the wonderfully evil Alan Rickman in almost anything.
“Why a spoon, cousin? Why not a sword or a knife or…”
“Because it’s dull, you twit. It’ll hurt more!” 
I also have a fondness for that Shakespeare-quoting baddie–can’t remember his name–in Star Trek: The Undiscovered Country.
I second Flashman.
The Joker. 'Nuff said.
Trulaine and Q from Star Trek.
Dishonest John from Beany & Cecil. Ya ha ha!
I’ll throw in Prof. Snape in the “Harry Potter” books. I don’t know if I’d say he was downright “evil”, but he isn’t very nice at all and yet people seem to love him all the same.
And he’s played by Alan Rickman again!
I don’t know what it is about women and Professor Snape, but that character has become such an unlikely sex symbol for every woman I know who reads Harry Potter or watches the movies. Snape drives them crazy, and the dude looks like an older, dumpier version of Trent Reznor!