"We are the Canadian Borg. Resistance would be impolite. Please wait to be assimilated. Pour l'assimilation en franšais, veuillez appuyer sur 2."
—A Livejournal icon
Psycho Gecko, the Villain Protagonist of World Domination In Retrospect, is a friendly and entertaining murderous lunatic. It helps that he likes wacky and bizarre evil schemes, like unleashing drugged up chickens in a restaurant or releasing the contents of a zoo to attack a superhero, but then he also murders a lot of people, including superheroes.
In The Gamers Alliance, Hannibal Losstarot is a teenager who flirts with girls, loves and respects his mother, takes his studies seriously, speaks politely, constantly trains with his elite guard, treats his servants and enemies well, often even preferring to not be called by his hereditary title. However, he is also the son of one of the BigBads and just as determined as she is to conquer the world under the Losstarot family's banner and will stop at nothing to make his mother's dream become a reality.
Dr. Horrible is essentially the nerd who does evil things to be a part of the cool kid's club. He especially comes off as this when the "hero" of the piece is a total douche.
Fawkes, leader of the Axis of Anarchy from The Guild.
Troy the Wendigo from Epic Tales seems like he might fit this despite needing to eat humans. Which is interesting, since humans only become wendigos if they resort to cannibalism in the first place.
In the burgrr.comARG the real BBQ Girill is awfully polite and pleasant to our protagonist for being a horrifying hybrid of woman and barbecue grill who's part of a To Serve Man plot that said protagonist is trying to stop.
Tales of MU (this): "Few people mistake a noble dragon for a nice one more than once."
In the Global Guardians PBEM Universe, Evil Overlord Lord Doom really is a pretty swell guy, if you overlook the entire "take over the world, tyrannical dictator" aspect of his personality. He's urbane, friendly, and sends get well cards to his enemies when they are sick or injured. He even runs a charitable organization that has helped millions of children in poverty around the world. Did we mention that he wants to rule the world and everything in it?
It's entirely possible he believes himself to be a benevolent dictator in the making.
The thing about Lord Doom is that he realizes that in order to enact his vision for a better world (and ultimately, that is his goal: to make the world a better place for everyone), some very unpleasant decisions will have to be made, and only he can make those decisions. So while he is ruthless, he isn't cruel.
Dark General Argon from Sailor Nothing. He may be an utter monster and a heartless, but he is never impolite and seems to genuinely respect both the heroes and Cobalt for their drive and abilities.
Ganondorf from Melee's End is polite even while kicking the good guys' asses.
Humon's Neils is a good example of this. This Affably Evil, bisexual Dane is the nicest guy you have ever met! But if you get on his bad side, expect emotional torture and a bullet to the brain, or bludgeoning with a blunt object (courtesy of his black lover, Duncan). Although, he does try to comfort those whom he is about to kill.
Dr. Diabolik of the Whateley Universe. Caring father, hard-working inventor, Benevolent Boss, and by his own daughter's count, directly responsible for the lives of over 15,000 people in his raids on middle-sized cities around the world. When he attacks Cincinnati, he secretly encourages the heroes to triumph over his weapons, and when highly stressful problems occur, he politely asks his minions for ideas and rewards them for speaking up. Still, he attacks entire cities, knowing that tons of people will be killed or injured.
When Dr. Diabolik's children were the target of protestors and media outlets, he called each one of them up, at their homes, at their workplaces, on their mobiles... and calmly, politely, and non-threateningly explained to them that while he sympathized with them, attacking children over such a thing was a decidedly cowardly act. After that, the protestors just... went away.
There are a few others in this vein, in the WU: one of those is Brigand, who deliberately targets corrupt organizations and people, and who went out of his way to ensure that people with weak hearts in a hostage situation would be able to receive medical attention if necessary. And then there are are the ex-supervillains who teach at Whateley...