Most major villains in Kaze no Stigma are very composed and polite even while making their destructive intentions clear .
In Mega Man Megamix, Dr. Wily makes it abundantly clear just how much he looks down on humanity. However, when it comes to robots and Robot Masters, he can be remarkably polite and respectful. Not only did he give Shade Man a serious talking to for endangering Roll once when she had nothing to do with his scheme, but in the Grand Finale series Gigamix, when Wily City was being destroyed, he entered Papa Wolf territory towards his robots. It's clear he would have fought and died alongside them had Shade Man not put him to sleep so Shadow Man and he could escape.
Tokyo Babylon and X1999, amongst their body of work, highlight CLAMP's apparent love for beautiful, charismatic, fashionable men doing good, honest work in the service of others with secret homicidal tendencies.
Sakurazuka Seishiro is a friendly, charming, and generally mild-mannered veterinarian...when he isn't killing people on government contract with his dark onmyoujutsu and feeding their souls to a demonic cherry tree.
Also Fuuma Monou, who's perfectly willing to indulge in "innocent enjoyments" when not busy reducing Tokyo into rubble bit by bit.
A couple of the antagonists in Saiyuki fit this. Homura may want to completely destroy and recreate heaven and earth, but he's genial and charismatic, and would rather Goku joined him than have to take him and his abilities by force. Ditto Hazel, only switch 'and recreate heaven and earth' with 'youkai' and 'Goku' with 'Sanzo.'
Patlabor: The Movie 2: One of the people behind the terrorist attacks, Shigeki Arakawa, refuses to confess anything. Shigeki Arakawa is also Affably Evil. He went to Kiichi Goto when Yukihito Tsuge decided to alter the plan and start a limited war that would topple the Japanese government. Shigeki Arakawa’s original plan was a harsh political protest that used limited and controlled violence. Goto also agrees with Arakawa’s observations on the reality of peace, war, and political leaders exploit chaos instead of using a measured response.
Greed, one of the homunculi who are collectively the antagonists of the series, will never hit a woman, has a policy for always saying the truth, is respected and loyally followed by his comrades, and can even be nice if he wants to. That's not stopping him from being a pompous, greedy bastard and performing dubious acts for his own sake. He ends up doubling as a Noble Demon, especially the second Greed, who ultimately ends up an Anti-Hero. It's probably because he's Greed. He is greedy for everything, which includes as many comrades/subordinates/friends as possible, as he explains in the 2003 anime, though in the manga and second anime, he is much more reluctant to admit this. He's quite protective of anyone or anything he considers his "property", and would rather admit defeat or run from battle than risk losing any of them to death or injury. Being a big humanity-hating jerk like the other Homunculi won't get him anywhere with that goal.
Father, the Big Bad, is seen as an Affably Evil Cloud Cuckoo Lander when he first meets the Elric brothers, but this doesn't last long.
Majin Buu as well. So cheerful and childlike that he doesn't seem to bear ill will towards anyone: he's just trying to have some fun; in fact, the moment it's pointed out to him that, you know, killing people by the millions isn't a nice thing to do, he (genuinely) promises to stop. At least at first... then his truly evil side takes over and he becomes an Ax-CrazyOmnicidal Maniac who is a legitimate threat to the universe at large.
There's also the robot worker in "The Return of Cooler".
Robot: Excuse me. Your attention please. If you'd all be so kind as to follow me. We'll begin chopping you up. (Everyone gets scared) No no. It's not what you think. We don't want to hurt you. We only want the energy from your bodies to power the Big Gete Star. So we just have to chop you up.
Also, Frieza's henchman, Zarbon, who is hinted to be a prince in the game Dragon Ball Z: Tenkaichi Tag Team.
Goku's father, Bardock, falls into this trope. He has a surprisingly relaxed personality for a Saiyan, and he visibly gets on well with his teammates, going as far to avenge them when Frieza's henchmen kill them. Oh, and he commits mass genocide for a living.
Androids 17 and 18 are probably the friendliest robotic killers you'll ever meet. At least, the ones in the main timeline are—the ones in Trunks' timeline are a different story.
Former Admiral Aokiji is incredibly relaxed and when he first appears, is able to have a polite conversation with the Straw Hats, even coming off as laid back if not lazy, not at all what they expected from one of the three great powers. He even gives the Straw Hats a chance to get away in exchange for him capturing Nico Robin, mostly as a favor from Luffys Grandfather Monkey D. Garp, though when the need arises he's quite the Chilling Opponent.
Admiral Kizaru is incredibly polite, as when he asked a pirate who shot a bullet at him, as it was passing through his head, where his subordinate was. When they replied by running away, he saw no choice but to kick a mangrove tree down in a light-based explosion. Light Is Not Good, indeed.
Kaku of CP9 is equally polite and very honest. Before his identity as a villain was revealed, many fans speculated that he would be the shipwright to join the crew.
Friendly Punch Clock Villain Mr. Two Bon Clay was a total asshole when acting as an enemy, cheerfully exploiting Sanji's weaknesses while mocking him about them and so on. Still one of the nicest entries under Villainous Crossdresser, even before his Heel-Face Turn. He is also completely bananas.
Hild from Ah! My Goddess. She is a goddess' mother, very playful, very powerful, likes to hug people...and the queen of Hell. Her affability is more potent than most on this list. It's also heavily implied that she performs some notable..."good" in her role — she effectively keeps Hell's more aggressive and (self-)destructive tendencies under wraps, and negotiated a cease-fire with Heaven. She prefers a much more subtle Deal with the Devil means of furthering her goals than the open warfare some of her underlings seem to favor.
The Earl of Millennium from D.Gray-Man is a usually-jovial, eccentric gentleman who loves his family. He also happens to be plotting to destroy the world. His army is also Powered by a Forsaken Child. His Noah lieutenants (especially Tyki Mikk) fall into this occasionally as well, but just as frequently fall out.
Fin Kruder of Rental Magica is so affably evil that Itsuki and Honami eventually comment about how, though he can terrify them, they don't really hate him, despite what he puts them through. Either that, or he's well-meaning, but just thatcrazy. It's hard to tell in his case.
A recurring theme with the villain Sunshine in the Kinnikuman series. At first portrayed as just a standard member of his Quirky Miniboss Squad, in a later arc, Sunshine is genuinely moved by the displays of friendship between two of the heroes, because it turns out he feels the same way about his own friends. He even goes so far as to declare "Friendship exists even amongst demons!" at one point.
Riful is on a permanent recruitment drive and will frequently greet her opponents politely, proceed to make small talk with them, congratulate them for their efforts in their fight, and give them tips on how to make a successful strike against her, all the while asking if they want to join her. When diplomacy fails, she just tortures them to the brink of death to force them to permanently give in to their Superpowered Evil Side, all the while lamenting the pain she's inflicting and what a shameful waste of resources the death of the tortured would be.
Riful: My goal isn't your death. I will just torture you, make you awaken and then make you my friends! But if I kill you I lose everything. [She joins her hands in supplication] Please understand, I really do not wish to kill you!
Kazutaka Muraki from Yami No Matsuei is a polite doctor who approaches people in the most sympathetic manner when he is not raping, cursing, and killing 13 year old boys, or conducting human experiments to bring his dead brother to life so that he may be the one to kill him.
The shinigami - Ryuk loves video games and apples and considers Light his roommate, Rem is actually a genuinely nice person to anyone who's won her affection, and Sidoh seems like an ordinary guy. No, they don't give much of a damn for human life, but seeing as they have to kill humans to stay alive themselves, it's somewhat justified.
Fate Averrancus is leading a group which is trying to carry out the destruction of his world. Despite this, he's actually a very sociable and polite young man, and Nodoka Miyazaki's mind reading artifact reveals that he would have rather preferred not harming anyone from her world, but the fact that she CAN read minds made her a liability enough to his plans that he has to eliminate her.
Earlier, there was Chao Lingshen, who gave the main hero the item of her eventual defeat as a simple thanks for his help. She was also more than willing to deliver a short, cheerful advertisement for her dim sum cart after a long pronouncement of evil towards the opposing army.
Many of the main Gundam villains are more or less affably evil. It'd be easier to list the utterly evil ones. Some of them are also Punch Clock Villains since they only fight because they are soldiers. Thinking about it...it's hard to come up with a straight example, as Gundam mostly lacks really evil people and many of its villains (and sometimes protagonists!) are mostly Well Intentioned Extremists.
If you want a straight example, there's Prime Minister Wong from G Gundam. A Manipulative Bastard with dashes of The Chessmaster and Mad Scientist (or at least, Mad Researcher), who loves red wine, chocolates, and sunglasses, and is also very polite and snarky to his rivals when in a good mood.
Takehiko Inoue's Vagabond has the Yoshioka clan, who seem to be one big happy group of True Companions who just have a penchant for cutting down or maiming those who besmirch the name of Yoshioka (and in the case of clan head Seijurou, ambushing those who could be an actual threat to them). The clan heads Seijurou, Denshichirou, and their right-hand man, Ueda Ryouhei, all get arguably sympathetic backstories, and they genuinely care about their followers and vice versa. Finally, when the first duel between Denshichirou and Miyamoto Musashi is interrupted by a fire breaking out and eventually consuming the dojo, Denshichirou tells Musashi to improve and then face him again in a year. (Unfortunately, Musashi ends up making far better use of that year than he does, leading him to cut down both brothers Seijurou and Denshichirou, one after the other, in their respective duels.) After Ryouhei decides to have Musashi ambushed rather than let him leave Kyoto, during the ambush, one of the minor henchmen of the Yoshioka actually gets a flashback scene where Denshichirou is giving the henchman's younger self a good luck eel, since his wife was going to give birth soon! (Unfortunately, what was supposed to be a seventy-on-one killing ends up with him, Ryouhei, and the rest of the seventy swordsmen of the Yoshioka school all being slaughtered by a single-katana-wielding Musashi.)
Get Backers has two: Kagami Kyogi and Kuroudo Akabane. Both act like perfectly normal, polite people — even while they're cutting people into bloody bits as a hobby (Akabane), or "observing" a 14 year old build WMDs and doing nothing to stop him (Kyogi).
Dio Brando—at least, when his bloodlust for the Joestar family isn't in effect. His greatest weapon isn't his vampiric abilities, or even his ability to stop time. His biggest weapon is his pure charisma. This trait is emphasized in Pucci's flashbacks, which are through the eyes of a man who only knows of Dio's charm and charisma, and not his crossing of the Moral Event Horizon.
Dio's affable evilness is debatable, as it can be argued that he was only charming Pucci and playing with his emotions so he would make a more effective servant. He is definitely Faux Affably Evil, though.
While Dio may hate the Joestars, he did respect Jonathan enough to want to give him a quick and painless death when he drove to cut off Jonathan's head and replace it with his own, vampirically-enhanced decapitated one.
An indisputable example with Wamuu from Battle Tendency: unlike the people he works for, Wamuu is extremely polite and engaging, showing nothing but the utmost respect towards his opponents even as he tries to brutally kill them.
Around half the cast of Baccano! falls under this, Lovable Rogue, or a combination of the two. Luck Gandor particularly exemplifies it, as he's generally an intelligent, amicable, and interesting bloke who is unfailingly polite even when he's telling someone he has no use for them whatsoever, and just happens to associate with absolutepsychos and do horriblynastythings to guys who cross him.
Claire Stanfield is another great example; he's perfectly friendly, charming, and polite to people who he isn't currently trying to turn into bloody messes of gore.
Dutch, leader of the Black Lagoon Company. A Benevolent Boss who, while showing no qualms about mass murder and human trafficking, takes good care of his employees, is usually calm and polite to everyone around him, and frowns on collateral damage.
Benny, Dutch's electronics guy. Pretty decent guy, would probably be great to have a beer and a few laughs with. His day job involves murder, drug running and grave robbing.
Also of note is Sir Alfred, a former Nazi bigwig who sent both a group of neo-Nazis and the Lagoon company against one another to find an old painting. When he and Dutch talk, they manage to keep things fairly civil with one another, even though Alfred does nothing to hide the fact that he's racist against Dutch and Dutch doesn't hide the fact that he'd like to stick it to the old goose-stepping codger.
Askeladd from Vinland Saga is a nice enough guy, despite being a vicious murderer and raider.
Omamori Himari: Shuten Douji. In his first introduction to the main characters, he has a casual conversation with them...while putting everyone else in sight to sleep, and fighting the heroes with the intent to eat them.
Naruto has Akatsuki member Kisame Hoshigaki, an affable and genteel sharkman who will rip your face off...but there's no reason to be rude about it. He's also arguably the Akatsuki's Only Sane Man.
Kabuto, Orochimaru's former Second-in-Command, commits crimes against humanity with hardly a blink and casually tortures people not only with acts but also with words but is also one of the politest characters the show has to offer, always adresses people with proper honorifics and sometimes even goes out of his way to help the heros... At least, before he integrated Orochimaru's cells into his body and completely lost it.
Nagi from the Mai Hi ME anime speaks in a relaxed tone and tends to address the heroines with polite words instead of taunting them. Naturally, a few of them suspect rather quickly that he's up to no good.
First, there's Gadved, an actually kind pastor who saved Van's life previously, and who still tries, in the most affable way possible, to convert Van to the other side, but he kinda goes a bit batshit when he enters the battlefield...
Then, there's Fasalina, an ex-prostitute. Her speech is considerably kind and soft-spoken (it doesn't hide her malicious intents), and she doesn't lose her cool for the most of time...well, until The Claw got killed, but even then, unlike the others whose Villainous Breakdown is going batshit, her breakdown is the 'affable' version of it: crossing the Despair Event Horizon. There's a really good illustration of Fasalina's affability in one scene. She and Carmen 99 are both seeking the services of the same electronics expert. While Carmen 99, one of the heroes, stiffs him of his full payment, Fasalina is a good tipper and thinks it terrible that someone would behave like that.
Also, in the same episode, contrast the Claw being a Friend to All Living Things and the behavior of the ruthless Jerk Ass hero, Ray. Despite the fact that at one point we see him murder a man, it is still impossible to see him as anything but a kind (maybe a little senile) old man.
Xellos is so calm, friendly, cheerful, polite, and oftentimes funny that it's sometimes hard to believe that he's part of a race that's Always Chaotic Evil — his kind feeds on the people's anger and suffering. But instead of hunting down and slowly killing humans, Xellos just tricks them and plays embarrassing or painful pranks while otherwise remaining so nice and helpful that his regular victims sometimes groan when he appears, but never tell him to get lost. This guy once wiped out a flock of dragons with but a gesture, and we see him shaken like a doll by some mortal he thoroughly frustrated...and smiling. He even saved some humans.
Red Priest Rezo is polite, well-mannered, and spends a lot of his time traveling from village to village, performing miracles as one of the world's best healers. He would also stop at nothing to heal his eyes which have a fragment of the Lord of Darkness sealed in them, even disfiguring his own great-grandson as an experiment and putting the lives of thousands at risk.
Amagiri, Amber's Dragon, is the quiet type of the Big Guy in personality, is really quite likable, and gets an amusing Please Put Some Clothes On scene with a hot female Contractor with no nudity taboo. He also participated in blowing up a series of embassy buildings.
The series also has human examples in Dr. Schraeder and Youko in the second season. He's a miniature senior citizen and she's a moe nerd, and both are friendly people, but both are completely devoted to the mantra of For Science!, and are utterly amoral in this respect.
The Hakushuu Dinosaurs as a whole, a football team in Eyeshield 21. While you can't really be "evil" in football, they try their damndest, using very dirty tactics.
Marco, the quarterback, is a polite guy, drinks soda, offers under-the-table deals to other teams for the best of everyone, sends flowers to the enemy before a game, and is fighting for the love of his life, the team manager, Maria. However, he doesn't care if he's crushing other people's dreams. Or bones. Of all the team members, Marco best personifies this trope: Nice Guy off the field, but on the field, he uses tactics that would put SS stormtroopers to shame, relying on Gaou and Kisiragi to injure the other teams' players.
Kisiragi is a wilting Ill Boy, prone to frequent fevers and illnesses. He has loads of respect for Marco, a huge man-crush on Gaou, and is self-deprecating about his own abilities while lauding those of his opponents. He also suffers from a bad case of Blood Knight and In Love with Your Carnage, and plays with the intent of dislocating the arms of other receivers.
And King Evil himself, Gaou. He respects the rules and other players, and is pretty harmless off the field (unless you pick a fight deliberately). On the field, he turns his strength Up to Eleven and deliberately tries to smash everyone in his way.
Giovanni from Pokémon Special. Sure, he's the leader of a criminal organization that steals Pokemon and performs horrible experiments on them, but he has never resorted to dirty tricks when it comes to battling. When he fights Red, he's courteous, praising him and giving him pointers while beating the snot out of him. He even earnestly offered to fight at a disadvantage. This makes him a damn good villain because it shows he is where he is because he's just that strong. Oh yeah, and he really loves his son. This may show why he has a slew of extremely loyal Elite Mooks that refuse to take orders from anyone else claiming to be the new head of Team Rocket. In the HGSS arc, Carr claims to be the new leader of Team Rocket just to have his ass knocked off his seat, with the Four Generals saying that only Giovanni is fit to rule them.
Warrior King Guitar from Violinist of Hameln (the manga version, not the anime) is a heartless, thoroughly egotistical, mass-murdering monster, as befits a mazoku general, but his cheery, somewhat goofy demeanor, and fake humility make this less apparent than his colleagues. Well, until he starts torturing people while remaining as upbeat and polite as ever.
Mister Wiseman from Until Death Do Us Part is very courteous towards his enemies. He's also a college professor and criminologist when he's not plotting against people.
Many of the Demons/Supernaturals in Umineko no Naku Koro ni qualify. Ronove, Gaap, Sisters of Purgatory, Dlanor, Zepar/Furfur and Featherine all demonstrate on a few occasions that they are much more human than they let on. Most of the Witches play with this trope at points (when they aren't cackling at murder) ...and then there's Erika.
She swoops in to save Ange in the last chapter and gives her some advice because of her pride as a "detective" (which is also why she accepted a possible fatal challenge from Beatrice). Then again, there are more FaceHeelTurns, HeelFaceTurns, JerkassFacades, and personality twists and turns in this game than you can shake a stick at.
Saiou from Yu-Gi-Oh! GX was like this too throughout most of the second season, until near the Season Finale when the Light of Ruin took over him completely, turning him into a monster.
From Kenichi: The Mightiest Disciple, we have Agaard Jum Sai of Yami. Unlike his disciple, Tirawit Koukin (who is by far the coldest bastard in Yomi), Agaard is almost always smiling and cheerful, and in Chapter 397, he actually thanks Kenichi for being such a good disciple to his nemesis Apachai.
Fortis of Huckebein from Magical Record Lyrical Nanoha Force, who is quite the cheerful, charming, and polite fellow, even when he's talking about the atrocities the Huckebein commit while trying to convince Tohma to join their criminal group.
In ROD the TV, Joker is a perfect example of this. He is, for the most part, polite, well educated, and very civil. Except for the part about wanting to brainwash the entire planet and how he will manipulate anyone to reach his goal, he would be a rather nice person. He is even willing to have his personality obliterated for the sake of his ideal.
Mononobe from Eden of the East. When he fails to recruit Takizawa Akira into his Evil Plan to attack Japan with missiles, he simply lets him go. When Takizawa beats him, he simply gives up and has a nice chat with Takizawa. This is mostly because he is a Well-Intentioned Extremist who actually believes his plans are the best for the country. Takizawa himself never actually blames him or calls him out on his extremist views; instead, he asks Mononobe for advice, and agrees with his Evil Plan, but amends it so that nobody dies.
Goemon in Yaiba, who, after all, enjoys drinking sake, and wouldn't hurt animals no matter what. Also, Kaguya, who flirted with Onimaru...before parrying his wind slash with her fan and tossing a huge ki blast at him.
Charles and Ray from Eureka Seven. They're friendly, worldly, nice mercenaries for hire, who just happened to have a grudge against the good guys and were paid to take advantage of that. They honestly treat Renton better than most of the main characters, and they even plan on adopting him as their own son. Their deaths are some of the saddest moments in the show.
Sebastian Michaelis in Black Butler, although less so in the anime than in the manga. He's so good at it it's easy for some fans to forget or overlook that he's a soul devouring demon after a young child's soul.
Kirby: Right Back at Ya!'s Customer Service/NME Salesman is so polite and funny at times that it's easy to forget that he wants Kirby dead, like Nightmare.
And speaking of Nightmare, even though he's bent on galactic domination, he's an oddly enough laid-back sort of tyrant who spends much of his time in his lair. He treats some of his employees, like the NME Salesman, with respect, and those he respects treat him with deep respect as well.
King Dedede is a bigger Jerk Ass than his games' counterpart, but still leans as something of a redeemable Man Child, most of his actions too ineffectual to be seen as monstrous and he still has a few friendly moments with Kirby and his usually abused minion Escargon.
Old Super Robot Genre shows usually has a villain like these. The most standout example are Getter Robo and Great Mazinger, whose their motif for what they do in the show can be simply put as "They are not human." Otherwise, they are just as honorable and heroic as the heroes.
Akihiko Kayaba of Sword Art Online is kind, if a little distant, and congratulates the players when they finally beat the game. He also trapped ten thousand people in a death game, and almost four thousand of them die before the end. Contrast the villain of the second arc, Nobuyuki Sugou, who only ruined (ruined, not killed) the lives of three hundred or so people, but is seen as far worse by the audience due to his malicious and selfish motivations, not to mention that he captures Asuna and only holds off raping her because he thinks invoking a Hope Spot will break her more.
Reiner Braun from Attack on Titan is a justified case. If his side weren't bent on wiping out mankind, he'd probably be a hero and is hinted to have always wanted to be one in the past. Just because he's The Mole and a mass murderer doesn't mean his kind and selfless personality is fake. He's a genuinely nice guy, who happens to be working for the bad guys since a young age, and crushed by guilt over what he's had to do for his mission.
As much of a dick as he was pre-Heel-Face Turn, Mewtwo from Pokémon: The First Movie was, for the most part, pretty well mannered, despite the whole kill all humans and Pokémon and replace them with clones thing. The English dub makes it a bit more apparent where Mewtwo basically acts like a Pokémon version of Dr. No. * Speaking of Anime/Pokemon, Meowth, Jessie, and James have become this in large degrees in the later seasons to the point where James and Meowth in particular come off as more of the anti-hero than actual villians. This could explain why their "attempt" at becoming threatening led them to take a small absence from the series and come back as their former affable selves.
Sakyo from YuYu Hakusho is this. He's polite and quite a gentleman, especially to Shizuru. When it comes to gambling, he's also shown to be honorable and fair, especially when he lived up to the agreement to take his own life if Team Toguro lost to Team Urameshi, which they did. Despite these traits, he's sadistic, cruel, and sociopathic to his victims, not to mention, he performed his wager by first blocking the exits of the stadium everyone was in, then setting it to self-destruct.
Yoshii, the first villain from Texhnolyze could fall into this category. He's polite and agreeable to just about everyone he meets in person (and he even saves the life of another character at one point) but that doesn't stop him from killing people and trying to start a civil war in Lux for reasons that make so little sense they might as well be no reason at all.