Mike Toreno from Grand Theft Auto: San Andreas — who, it turns out, is a fairly nice and friendly guy, who just happens to be the scariest person you'll ever meet. It helps that he has the best line of dialog in the entire game:
Torino: I wanted to see what you were made of. CJ:(Angrily) What it look like I'm made of? Pudding? Torino:(Calmly) No. Anger, and hate. That's why I like you.
And then there is CJ himself, who will have no problem shooting or running over unarmed civilians, assassinate people who never did a bad thing to him and generally steal, maim and kill. However, most of it is because he is given no other alternative in order to keep his family—blood and otherwise—from being harmed and is genuinely nice and polite (outside of whatever the player makes him do) to the people around him. Compare this to Tommy who alienates and belittles his inner circle and Claude who repays the women who save his life by killing the brother of one and then shooting and killing the other for talking too much.
Graham from Castlevania: Aria of Sorrow. Ridiculously pleasant to the protagonist, until he realized the Protagonist is his primary enemy, but he is the Big Bad and trying to take Dracula's power for himself. Doesn't excuse rudeness, though.
President John Henry Eden from Fallout 3 has a kind voice broadcast across the wasteland on Enclave radio; it will lift your spirits as you traverse the wasteland hearing about how the Enclave will come and begin to transform America back the way it was before the nukes fell (unless you played the other Fallout games). He is similarly polite and gracious when you meet him in person. What he doesn't mention is that not only is he a ZAX supercomputer, his bold new vision requires killing off everyone.
President Richardson of Fallout 2 is very similar in character, greeting the player in a friendly manner ("I am the president of the United States, and you are...?") and then going on to explain his plan of genociding the entire continent with a virus he intends to release. He's also so gullible that you almost feel bad for him when you have to kill him to get his security card. If you pick the right conversation paths, he admits that he really doesn't like what he's going to do and derives no pleasure from it, but he's come to accept that it is ultimately the right thing to do (to him, anyway).
The player can easily become this trope if played evil while still picking the friendly speech options.
And Alister Tenpenny for that matter. He wasn't "cool", but he was polite and kind.
Tenpenny specifically asked Burke to evacuate Megaton before blowing it up. Burke... didn't really bother, but Tenpenny doesn't know that. Tenpenny's only truly negative point is being a ghoul hater... and to be perfectly fair to him, the ghouls in the tower's vicinity gave him very little reason to be polite to them. Other than that he's largely just not terribly bright, in spite of being the boss.
The add-ons to the game have their fair share of affably evil characters too. The Pitt gave us Ashur (assuming you see him as evil after certain reveals towards the end of the DLC), while Point Lookout gave us Tobar.
In Fallout: New Vegas, this includes most senior Legion members (particularly Legate Lanius) and Benny. Old World Blues gives us Doctor Mobius, though it's revealed he's not truly evil, and that the Think Tank are the real Big Bad of the story.
Dr.Robotnik/Eggman from Sonic the Hedgehog has his moments of this trope throughout his various depictions. This is most noticeable in Sonic X and its subsequent comic, and in the movie, where he makes a big show of holding the President and Sara hostage, but gets along with them marvelously well whenever Sonic isn't around.
In Sonic Heroes, he is described as "a romanticist, a feminist, and a self-proclaimed gentleman", but also as possessing a mania that often obscures this side of his nature.
In the ending of Sonic Generations: The classic verson, having learned that he never defeats Sonic, ponders upon pursuing a career as a teacher instead.
Within five minutes of meeting you, Police Chief Damon Gant has probably given you an affectionate nickname, laughed uproariously at something funny you said, and extolled to you the many virtues of swimming. Oh, and he framed a child for a murder he committed so that he could use her apparent guilt to manipulate her sister, the Chief Prosecutor, essentially giving him complete control over both the police and the prosecutor's office. But other than that, he's a nice guy. In-game dialogue states that if you're short on cash, he's the man to ask to borrow from.
Investigations: Ernest Amano is a pretty friendly and conciliatory person who happens to be a Corrupt Corporate Executive whose business group is in cahoots with an international smuggling ring. He even tries to get his guilty-as-sin son acquitted for murder, but drops the idea when charged with obstruction of justice.
FFIV's Rubicante is quite polite and articulate for an Archfiend. He restores the HP of the party prior to battling them, he's outraged when he learns of his Mad Scientist subordinate Dr. Lugae's cruel experiments on humans, and his first appearance has him easily defeating ninja prince, Edge, where Rubicante praises his current abilities and potential, and encourages him to train and become stronger and then return for a rematch.
FFV's Gilgamesh was an over-the-top goon whose respect for the heroes' fighting talents after they'd beaten him a few times grew into actual affection to the point that he sacrificed himself (with a strangely amusing Final Speech) to protect them from one of the Big Bad's meaner minions. He also has a devoted fanbase, probably explaining his many, many reappearances.
FFVI's Ultros arguably qualifies. He engages in Too Funny to Be Evil (if unintentionally via his attempts to be a competent villain - but only ever earns himself Quirky Miniboss Squad status, if that), and during your third fight against him, he even gets guilt-tripped into letting Relm paint him by Terra (but he does continue pummeling you until you use the Sketch ability). He feels so guilty, he even permits the use of Relm's pet name for him ("Uncle Ulty") very briefly.
Final Fantasy XII's Vayne Solidor is cultured, polite, affable to the public, and an extremely talented speaker. One entire scene centers around him getting so fed up with a merchant refusing to drop "Lord" from his title, he invites him to dinner at the palace! Arguably, Vayne isn't so much evil (though he does have his moments) as a Machiavellian statesman, ruthless in his pursuit of personal power and glory.
The Ur-Quan Kzer-za of Star Control, while the rulers of a brutal slave empire spanning a quarter of a galaxy, are actually pretty nice guys when you talk to them. They do any of the following: fully accept surrender and mention that your crew will be treated well and taken back to Earth, acknowledge your status as a Worthy Opponent, mention that they are protecting their thralls from much, much worsethingsin the galaxy, and entreat you to go home should you win against them, as the more of their ships you destroy, the less likely they are to win their current war with their Omnicidal Maniac kin. They also give the races willing to fight for them an absurd amount of autonomy, find a new (and very nice) homeworld for the defeated race, avoid wasting resources whenever possible, accept the wishes of the races they've beaten, and generally conduct themselves with honor whenever possible. All of these things, quite naturally, aid in their downfall. Moreover, it's an established fact that they never insult foes. And this fact can be exploited by PCs too.
The Kzer-Za let you go unmolested for warning them about the Neo-Dnyarri. This does allow you to go right back to opposing them, but it does make sense even from a less affable perspective: the Dnyarri are the reason the modern Ur-Quan are the way they are, and the Ur-Quan remember very well. Anything you do, the entire Doctrinal War between the Kzer-Za and the Kohr-Ah, is small fry compared to the possible return of the Dnyarri.
The Kohr-Ah themselves are also relatively nice for a bunch of Omnicidal Maniacs. They make no attempt to hide their intentions, but they are just as polite as their Kzer-Za bretheren, and when speaking to them, you get a sense that they don't really hold any malice towards those they kill. When they attack, they also allow their victims a chance to perform any "last rites" that are traditional when one is about to die. They also believe in reincarnation, and one way they justify their genocide is their belief that everyone they kill will eventually be reborn as a Kohr-Ah.
The villains of the forgettable gameNight Trap, who are a nice family who donate to charity and have friends over. They eat the friends, and the charity they donate to is zombie vampires...
Tsukihime - A certain vampire victim turned vampire herself is an example. She is a nice, sweet girl, who honestly loves and cares for the main hero. She just happens to require sucking blood to live, is beginning to get a perverse enjoyment of it, and happens to sometimes get the sudden urge to go "fufufufu". She's rather pitiable, and Shiki agrees. It's Satsuki, if you hadn't guessed, and he pities her so much that he grants her the only peace he can...a quick death.
Dimentio from Super Paper Mario is a good example of this trope, always wearing a pleasant smile and showering the heroes with compliments. "Well met, lady. Your beauty is as refreshing as a slap to the face on a crisp winter's day", or "If they make greeting cards to thank people for helping with evil plans, I owe you one."
Count Bleck is also a good example of this. He uses polite language and never punishes his minions physically.
King Dedede, of the Kirby games, is almost always the villain through being possessed, or a misunderstanding (on Kirby's part!). Awesome examples include Kirby 64 The Crystal Shards and Super Smash Bros Brawl. King Dedede saves a few characters' lives, and then hugs Kirby when he finds out that he's OK.
Dagoth Ur, the final boss of The Elder Scrolls III: Morrowind. When you confront him, he politely explains why his plan to spread blight disease and create a giant magical killer robot are really in the best interests of his people. He answers every question you put to him (whether he's telling the truth, lying or mistaken is up to the player). Finally, he offers you the opportunity to buff yourself up before you start to fight him. Though the last part is largely because he needs Wraithguard (the gauntlet you need to hold the weapons required to thwart him) in order to bring his plan into action. And if you approach him without the items needed, he'll politely point out you have come unprepared and that you can not win as you are, suggesting you return when ready to face him.
Most, if not all, of the Dark Brotherhood are likable people (save for maybe M'raaj-Dar), if you can get past the fact that they're all murderers.
As well, some of the Daedric Princes (like Sheogorath) can be quite pleasant.
Even more true for the Dark Brotherhood in The Elder Scrolls V: Skyrim. In a few centuries of isolation, they have lost most of their dark and dreadful mystique, and apart from a really special sense of humour, they often look much more like an endearing Ragtag Bunch of Misfits than cold-blooded assassins. The first time you meet the team, they are actually laughing together and joking on their last missions. The character design is really impressive - they are assassins and killers and are very obvious about it, they have a morbid sense of humour, and yet they are passionate and full of life (well, except for Babette) people you can't help liking and feeling loyal to.
Albert Simon, the primary villain of the first game, has the appearance of an elderly British gentleman and often acts the part when he's not brutally slaughtering anyone in his way. When beaten, he acknowledges that you're better, and heals you up. When you finally defeat him, his biggest regret is that he didn't get a chance to show you the new world he was going to create. Not in a spiteful "look upon my works ye mighty" way: he really thought he was creating a paradise, and wanted the heroes to be able to enjoy it with him.
The sequel's big bad, Kato, fits this trope, too. He considers Yuri his friend, and tells him so, even after Yuri fatally wounds him in battle.
The Sniper slips into this, given his credo about his line of work: "Be polite, be efficient; have a plan to kill everyone you meet." That being an old US Marines Badass Creed.
The Engineer is a much more obvious example: he's described as an "amiable, soft-spoken good ol' boy", and generally behaves as such, but, at the same time, doesn't have any concerns about killing people based on the dominant colour in their wardrobe.
The RED Spy, specifically. He is a cold-blooded killer, and hot-blooded lover. Of the BLU Scout's Mom.
You'd think that The Medic was one, but no. Healing is just a side-effect that pays the bills for his evil experiments.
The recent Meet the Medic video mixes it up a bit, changing the Medic from Faux Affably Evil to Affably Evil With Great Emphasis On "Evil". While operating on The Heavy, they share some pretty friendly banter. It's quite clear, however, that he has no problem endangering The Heavy's life with his experiments. After all, he claims that the sound of The Heavy's heart exploding is simply, "The sound of progress!"
MERASMUS!, the Magician responsible for hauntings, hexes, curses and being Soldier's roommate.
Many of the villains in Metal Gear have a lot of innocent blood on their hands, but many of them are surprisingly nice people if they encounter Snake in a situation where nobody would gain anything by fighting. Sniper Wolf, Vulcan Raven, Grey Fox, Fortune, Olga, The Boss, Ocelot (in MGS and MGS3), and Big Boss murdered dozens of people and took part in large scale terrorism. But you wouldn't suspect that when you meet them at any place where they are not trying to shoot you. But then, you meet people like Psycho Mantis, Vamp, and Volgin, and realize that some people just need to die.
The hack-and-slash offshoot Video Game/Metal Gear Rising: Revengeance presents Senator Armstrong, an amiable politician who speaks fondly of his college football days, his service in the U.S. navy and how he's perfectly fine with Raiden joining his cause. This is only further amplified by Armstrong believing in the same general ideals as the protagonist Raiden, albeit with less concern for casualties.
Though probably not intentional, most of the members of Desperado are also likable. They're obviously homicidal psychopaths, but they also show heaps of personality and never hide how much they enjoy their job.
Drakuru in World of Warcraft. Turns out, he was using you all along, which isn't a big surprise. He accomplishes his goals and is transformed by the Lich King himself. What is a surprise, however, is that he immediately asks for your forgiveness for the deception and invites you to be his right hand man, both out of gratitude and to make up for tricking you, and because the Lich King apparently has some interest in you personally. The story continues in later quests, ultimately ending in you betraying and killing him. His "gratitude" would have involved you ultimately being turned into his right-hand ghoul, the lowest rank of the Scourge, while he would be living it up as a Death Knight. It is worth noting, however, that despite being (disguised as) a ghoul, Drakuru didn't treat you as such. Ghouls are footmen at best, but you'd have been an officer, far above the cannon fodder and privy to Drakuru's most guarded secrets. The guy really believed he was doing you a favor. It could also be that the ghoul graphics used for your character just represent generic undead-ness.
Nexus-Prince Shaffar, the final boss in the Mana Tombs, also comes across as this. As you barge into his operation, his reaction is to say that he was not expecting company and, somewhat apologetically, that he is preoccupied, but promises to tend to you..."personally", all the while using a tone as though he's about to break out the champagne and offer you a drink.
Persona 3: Shuji Ikutsuki, hands down. He's kind, he makes silly puns, he always answers your questions and generally aids in the mission to bring down the twelve Arcana Shadows. Although it turns out that he's just been using the protagonists to bring about The Fall, in addition to being fairly clearly insane. A cutscene in FES reveals that his jovial personality was indeed genuine, showing him making up puns in complete solitude where there would be no need to maintain a pretense. Even his motives for bringing about the Fall seem more along the lines of Dark Messiah, rather than Omnicidal Maniac.
Subverted with Adachi in Persona 4. Whenever you meet him in the game, he's frequently shown to be clumsy and incompetent, but a pretty nice and reasonable guy. He even lets the protagonists go in order to pursue Namamtame. This is all an act. He's actually an Ax-Crazy who committed the murders largely for the fun of it, and would be quite content to let the world succumb to the world of the shadows. He even mocks his victims when recounting his experiences with the protagonists. That said, he can be pretty funny in an insane, monstrous way.
GLaDOS from Portal. The computer attempts to put you at ease and encourage you, right up until the moment that it needs you to die. It even thanks you while it does it.
Wheatley from the sequel after his betrayal. Even when you're within 20 feet of his lair, he reveals a mashing device, and politely asks Chell if she wants to kill herself rather than have him do it. That, and how could you possibly be horribly evil when Stephen Merchant is your voice actor??
Wheatley: Think of it not as a death trap, but as a death option!
Aperture Science's main goons are laser-guided, talking Sentry Turrets with gentle, childish demeanors. Supplementary material says they were originally created to protect children; their dialogue in combat evokes a warped game of peek-a-boo.
Vladamir Lem from Max Payne. Starts off as Max's ally in the first game, but by the second, he fills the role of the Big Bad. Never loses his suave demeanor or his cordial disposition: "Max! Dearest of all friends..."
Vladimir Lem:(answering machine) I'm coming to kill you, old man. You really know how to piss me off, you know...Would it have killed you to say "thank you" for once in your life? To say "Vlad, my son...can I call you my son because I sure do love you like one." "Vlad my son, you are a true prodigy. Everything you touch turns to gold." Oh...wait, it is going to kill you! I'm done doing your dirty work for you. You should be proud. I have learned all you've taught me. I'm coming to show you. ... Vladimir Lem: What the fuck is wrong with you, Max? Why don't you just die? You hate life, you're miserable all the time, afraid to enjoy yourself even a little! Face it, you might as well be dead already. Do yourself a favor, give up!
Chaos Lord Eliphas the Inheritor from the Dawn of War series is a very suave, witty, and charismatic villain. Widely considered one of the most popular characters in the series.
In the new Dawn of War 2 expansion pack, Retribution, the Great Unclean One is decidedly gregarious, laughing and chortling... as he infects anything he touches and cleaves everything in two with his giant, blunt, filth-encrusted blade. But he loves you! And he just wants you to feel Nurgle's love!
Ulkair, the Big Bad of the earlier Chaos Rising is simply an unusually powerful Great Unclean One, so it's not too surprising he fits this trope. He seems to genuinely enjoy fighting the Blood Ravens in a jovial way even as he chides them about how it's useless to resist him, and takes his defeat in good humor — after all, in the long run, they're doomed either way, so why should his losing matter?
Jeremy from Fatal Hearts is polite, charming, studious, a diligent worker in both his mundane job and his more esoteric activities, interested in the environment and the welfare of others, and an all-around gentleman. Unless he thinks you're too stupid to live. In which case, he kills you.
Dr. Killjoy. He's modeled after Vincent Price, so he's naturally the most charismatic individual in the two games; in fact, he's so urbane you might just forget that he's a mass-murdering Mad Doctor with a fetish for film projectors and blood. Plus, being a psychiatrist, he genuinely wants to help cure the main character- it's just that his methods are just a tad...unorthodox.
Blackmore was a particularly affable character in his own right: in all of his dealings with Torque, he treats him like a somewhat misguided little brother - appropriate, considering that Blackmore is a Split Personality of Torque - and continually tries to convince him to join his gang rather than kill him. And then, there was the way he called Torque "my little one".
The Reapers from The World Ends with You tend to be rather normal people, essentially (aside from the Officers, most of whom are sadistic and/or certifiably insane), who are just doing their job - which happens to be permanently erasing the souls of the dead from existence to prevent themselves from meeting the same fate. Kariya, for example, is rather friendly, and 777 lives a double-life as a popular rock star thanks to the Reapers' ability to exist on the living and dead planes.
Shiranui Gen-An gets this treatment in the Samurai Shodown series. He boasts of becoming the King of Evil. Yet at the end of the day, he's just a disfigured oni-like creature with a glove inspired by Freddy Krueger, a loving wife, and kids he even brings to work. See his ending in Samurai Shodown VI (American numbering).
Helena Blake, a crime lord in Mass Effect 1, may qualify. She's polite, friendly, and charming in her dealings with you. In fact, if Paragon Shepard convinces her to disband her organisation, she shows up again in the second game, having genuinely reformed and became a charity worker.
The same goes for Aria T'Loak in Mass Effect 2, her mild god complex aside, she is entirely reasonable and rather friendly. She's also a ruthless crimeboss running a stationwide society built on slavery and murder.
This might be a possibility in Mass Effect 2 with the Illusive Man. He runs a pro-human organization, Cerberus, that committed awful acts that includes the assassination of one of the candidates of a political party, running live human experiments, turning a helpless little girl into a biotic killing-machine, signing off further plans to wire autistic individuals into machines to control geth, all the while silencing anyone who knew too much about them. Despite all that, he's very polite to Commander Shepard when they first met and he uses his charm to have the Spectre join their cause. He also saves your life, at the cost of billions of credits and nearly two years of hard work, for no other reason than that he believes your story about the Reapers and wants to help you save the galaxy. Or so he claims. Near the end of Mass Effect 3, Shepard discover secret Cerberus files where the Illusive Man freely admits that he was simply exploiting this trope in order to get Shepard to go along with his plans.
Lucifon (a.k.a. Satan) of Princess Maker 2 appears less a sinister Anthropomorphic Personification of evil and more a guy you can have a (rather corrupting) drink with. It's arguable that he's just doing his job, though he takes a certain pride if he can get your daughter to take his place at the end of the game.
Dr. Ned (who is not Dr. Zed), from the DLC for Borderlands. He offers you brownies before remembering that he's trying to kill you for discovering his evil plan.
Similarly, General Knoxx from another DLC falls under this. He believes to be the Only Sane Man in his group and actually apologizes over having to kill you.
There is also Mr. Shank. Despite having a really scary name and having an army of cannibal escaped convicts, he's actually a pretty nice guy. Really, he's only trying to kill you in self-defense. He watches you on security cameras while talking about how one of his henchmen who he is not in love with or anything makes great chilli-cheese fries. When you kill him, the person who contracted you to kill him starts getting all teary-eyed remembering the good times they had together.
Fire Emblem: Radiant Dawn sees Sephiran, who is introduced and interacts with the protagonists as an almost saint-like figure in the first game, a devoted servant of the Goddess Ashera, until it is revealed that he is the mastermind behind the plot to awaken Ashera and wipe out all life with her divine wrath, having lost faith in the world after the Serenes Massacre. Also, he's over 1,000 years old.
Gnarl in Overlord always acts in a calm, polite manner, something that simply doesn't cross the minds of most of your other minions. Even after siding with the original Overlord, and betraying you at the end of the first game, he still refrains from berating the player, and, instead, compliments you on doing a good job.
hiroshi42: "[The Bay12 commnity will] routinely talk about kitten slaughter, the best methods to immolate creatures without destroying their stuff, or how to produce 'children' with personality problems beyond the dream of psychoanalysts but no one is going to insult your mother."
Tales of the Abyss has a lot of these, since nearly every antagonist is a Well-Intentioned Extremist to some degree. Van Grants in particular: while he has a fair few Kick the Dog moments when he first shows his true colors, outside of this he is polite toward the protagonists, and offers genuine praise to Luke and Tear when they become strong enough to pose a serious threat to his plans. He was also a very kind and devoted elder brother to Tear, and after his betrayal Luke still sees him as more of a father figure than his actual father.
Hazama, from BlazBlue, is so friendly-acting, polite, and funny at times, that it's easy for the audience to forget that, since he is actually Yuuki Terumi, he's also the kind of person who's crosses the Moral Event Horizon for nothing but the sheer evilulz before he's even woken up.
Same goes to Relius Clover. For all his depravities in the name of science, he conducts himself in a very stoic and very calm manner befitting of his position as a Colonel. He also keeps his calm better than Hazama.
Graf Michael Sepperin from RosenkreuzStilette is truly a nobleman at heart... and a Well-Intentioned Extremist at that. He organized the coup against the Empire and is even willing to become the Devil himself in order to protect Iris, and he doesn't underestimate Tia's willingness to protect those she loves without letting anyone be sacrificed, nor does he underestimate her well-enough knowledge that there's no sense in fighting for the Empire. And after his defeat, he tells her that she can find Karl in his prison and is even willing to let her know that Karl himself made an attempt on Iris' life.
And speaking of Iris, she earns a spot in this trope as well. She's very polite and sophisticated, even if she orchestrated the whole war and killed her own father and had Karl imprisoned for his attempt to kill her. Her friendly demeanor even allowed all of RKS to trust her without knowing she started the coup for kicks.
Chaos Shogun Kitsune treats his fellow Yokai with deep respect and tells them not to worry when the hero is coming to Yokai Island without heeding his warning and tells them that they have a guest to prepare for. Even when he wants to claim the island for all Yokai by stealing the Hanzamune Sword and using it to free the O-dokuro, he's rarely if ever pointlessly cruel.
Chaos Lord Wolfwing isn't really that evil, he's just a lonely guy who wants to build his own clan of Werepyres so he won't have to feel so alone. Even if he's willing to cause Chaos and Chaorruption to do so.
Zahart, despite being willing to have his Djinn Tibicenas, the eighth Lord of Chaos, do away with others just to remove them from his search for the Heart of the Sphinx, is nice enough to answer the hero's question about what uncovered the ancient city that the Sandsea oasis community is just part of. When Zhoom interferes with his attempt to dispose of the hero after that, Zahart is even nice enough to give in to Zhoom's demands for him to release his friend, and orders Tibi to release him / her. Later, he is facing away from his slave while ordering Tibi to do away with him after receiving the Heart of the Sphinx, possibly because it's suggested that even he can't stand watching brutal murders (the killing was so brutal that it was censored anyway).
Master, while planning to use the Skyguard to create enough mayhem to become a Chaos Lord himself, treats his minions with deep respect when he's not being called by his real name (since having that happen to him usually leaves him having his Dreamweaver make them relive their worst nightmares with her powers). He tells the Dreamweaver to give the recruit she casted her spell on plenty of time to realize how foolish his words were.
The Dreamweaver is also quite affable, acting polite especially while disguised as Granny V or Invidia.
A lot of Artix Entertainment villains are either this trope or full-blown Anti-Villains, especially the minor/holiday villains. Guffer, from Dragon Fable, also known as the Savage Outworlder, comes to mind.
Onimusha 2: Samurai's Destiny gives us Gogandantess!Greatest Swordsman of all the Demons! While the other Genma seem perfectly happy with eating children and destroying the mortal realm, Gogandantess' only goal through the whole game is to prove that he is indeed the greatest swordsdemon around by beating Yagyu Jubei. He acts with chivalry and honor, at one point saving the life of Oyu and—aside from an impenetrable magical shield—faces Jubei on equal footing, one-on-one. This conduct earns Jubei's respect and he even honors Gogandantess' last request; to tell Gogandantess that he is, in fact the Greatest Swordsman of all the Demons.
Tor Anwyn, the Warlock promoter of Might and Magic VII. We know he is evil because of the other persons and things associated with the Path of Dark in that game, and because the Heroes game put the Warlocks as evil since Heroes I. He's always polite, even when asked to promote a Light-aligned party - where other such promoters are inclined to disparage you as a do-gooder, not cruel enough, or not cold-hearted enough for the job, he reacts by apologizing and explaining that the way of the Warlock requires you to be on the Path of Dark, so he's simply not able to oblige. He's not exactly harmless, though: what all that means is that he trains other evil folks into becoming more powerful.
Uthar Wynn and Yuthura Ban, headmasters of the Sith Academy in Knights of the Old Republic are well-spoken, polite, and don't seem to be powered by the constant combination of anger, malice, and batshit crazy as most of the Sith you'll encounter. Uthar will gladly acknowledge a job well done, and congratulate you on your progress. Yuthura is quite patient and erudite when explaining the Sith Code, doing more to explain the Sith in six minutes than Lucas bothered with in six movies. Still, they are Sith, and are pleased when you kill off one of your fellow students or aid them in a double cross you can double-cross both of them by playing them off one another. Uthar's "final test" for a student is to have them kill an acquaintance in cold blood, for no other purpose than to prove their superiority. Depending on the Player Character, the situation can end with one of them dead and the other returning to run the academy, both of them dead, or Uthar dead and Yuthura walking away from the Sith.
Hades from Kid Icarus: Uprising definitely qualifies. Sometimes, Pit will be fighting against him and his forces; other times, he'll be sharing humorous banter with Pit, Palutena, and the other gods and goddesses. Even when Pit is fighting against him, he still remains nonchalant. That said, he is still very much evil, and crosses the Moral Event Horizon near the end of the story when it's revealed that he's deliberately causing humans to war against each other so he can harvest their souls to power up himself and the Underworld Army.
More of a subversion, he qualifies in the early chapters, but even before he causes the Moral Event Horizon quickly turns into a character that annoys everyone else at best, and shocks them at how much of a monster he is, even to the point that when making up a story about himself and his motives he can't paint himself in a good light.
Patches from Demons Souls and Dark Souls. The guy tries to murder you, possibly twice (in each game), is directly responsible for killing two other characters, but is pretty amusing and chatty, and ultimately decides to give up on corpse-robbing and become a merchant.
In Baldur's Gate, Alatos "Ravenscar" Thuibuld, the head of the Thieves' Guild in the city of Baldur's Gate, invites your characters to his guild and offers them employment in stealing some particular McGuffins. He acts politely, but by the time you are talking to him, he makes it clear refusing is no longer an option after you have been there and seen him and the other members. It also turns out that the client who "ordered" this burglary was intent on disposing of the people hired to do it, and Thuibuld lets you and him nuke it out between yourselves, without particularly caring who wins but acting nice afterwards too.
In Baldur's Gate II: Shadows of Amn, Aran Linvail, the Shadowmaster of Athkatla, offers to make a deal with your party to get you ahead int he plot. He sounds very amiable and reasonable (even though piles on extra demands after you've already paid), and he might not even appear particularly evil if not for the reminder of the torture going on at the other end of his base. However ruthless he really is, one may assume he's still the lesser evil compared to your other option at this point, Bodhi.
In BG 2's Enhanced Edition, Hexxat is this as well. She may be a Neutral Evil thief and vampire with few compunctions about killing people for food, but she remains very polite towards the other party members, even sincerely apologizing for making them feel uncomfortable.
The Dragon in Dragon's Dogma. He is more well-mannered in his speech than you'd expect from a fire-breathing, world-ending dragon, even moreso than most of the other characters in the game. He'll even offer the Arisen a choice of just giving him one measly sacrifice in exchange for him leaving Gransys temporarily and as a bonus, immortality.
Darksol in Shining Soul is ever so polite, In fact most of the bosses are, but Darksol takes it one step further by going on about how darkness is like art and all you can do is admire the beauty.
The Boss from Catherine. He kindly serves you drinks, gives you advice, and even grants you a wish if you defeat him. Rather nice all around.
Trisha/Ishtar to the extreme. She creates this elaborate and deadly game, but is kind and acts as your host on the adventure.
CFW Brave from Neptunia, especially compared to his comrades. Before he is shown on-screen, he is even described as "more chivalrous than evil," and when he finds Nepgear and Uni in Endless Zone, he offers to let them go before attacking them.
Despite being a creepy, emotionally-impaired, antisocialStraw Nihilist who wants to destroy the universe, Cyrus of Pokémon Diamond and Pearl is pretty friendly to the player character. He praises your skill and compassion (though he considers the latter a backhanded compliment), makes small talk about philosophy and science and your ongoing attempts to thwart him, and outright gives you the Master Ball, just because he thinks you'll get more use out of it.
Minor villain, but the carnivorous plants in King's Quest VII: The Princeless Bride. They are incredibly polite to both Rosella and Valanice, and even give Rosella advice on how to get through the Wood of the Were-Folk. The only thing that makes them evil is, well, they are trying to eat Rosella and Valanice, and make no illusions about it.
Alexander from Amnesia: The Dark Descent, he's a gentleman who talks reasonably with Daniel, but he is also a deceitful and manipulative. He lied to Daniel that he knows how he can stop the shadow that's chasing him, and tricks him into torturing and killing innocent people to harvest their vitae, and his plan is to use the vitae to get back to his own world and leave Daniel to be devoured by the shadow.
In Robopon 2, Dr. Zeke finds Cody washed up on the beach and saves him, taking him to his house until he wakes up.
The Bonne Family from Mega Man Legends want treasure and are willing to do just about anything to get it, but they're all actually quite likeable and good-hearted when the chips are down. When they find out near the end that Mega Man Juno's plan is to eradicate all life on the island, they drop everything to help put a stop to it.
Hilariously, Crusader Kings somewhat encourages the player to be this. The game gives a number of bonuses for virtuous traits such as kindness and humility, but having these traits does nothing to stop you from conquering land through political manipulation and brutal conquest. Even if you can justify it with Realpolitik, the traits-modelling system itself will also occasionally cough up a soft-spoken and charitable young king whose favourite pastimes are raping women and putting severed heads on the end of pikes.
Seth, of the Street Fighter series is somewhere between this and Faux Affably Evil. While in part he is a vicious man with a massive inferiority complex, with an overwhelming desire to take control of the world, He is also seemingly very pleasant to talk with, kind to his subordinates, has an (albeit dry) sense of humor,admits to actually rather enjoy fighting (not in a Blood Knight way), and compliments those he deems worthy of battling him.
The Matrix Path Of Neo briefly has this with an unnamed Giant Mook who says, after Neo asks him for a key, "Please ? You may be an idiot, but I can't fault your manners."