Temoc was the High Priest of a religion which practiced Human Sacrifice and under the new regime is a notorious wanted terrorist. He's also a loving father who cares about Caleb's well-being (including asking about his love life) despite their differences in "politics". At one point, Temoc breaks into Caleb's apartment for a clandestine meeting and takes the time to make his son's bed and straighten up the place. Not to mention, he thinks he's doing the right thing and kind of has a point.
The King in Red is a terrifying deicidal sorcerer turned lich... and a great boss who looks out for his employees and citizens.
Don Vito Corleone from The Godfather. Along with the politeness and generosity that carried over to his film incarnation, it's also established that he really does prefer to negotiate, spending hours trying to resolve disagreements between other crime lords without reacting to any insults or jokes made at his expense. Plus, he's shown to be utterly revolted when he discovers that the film studio executive Jack Woltz spends his afternoons molesting young girls - to the point that it became one of the reasons for the decapitation of Woltz's horse, Khartoum.
The classic here is "Long" John Silver of Treasure Island. He is a lot brighter than his fellow pirates, wise enough to plan for his old age instead of spending the loot the minute he gets it as most of them do, and is visibly courageous when faced with impending death. He has a sense of honour, too: when he suspects Abraham Gray, the pirate who repented and rejoined the Squire's party, of telling tales, Captain Smollett's angry denial that Gray told or was asked anything is enough for Silver to consider the matter settled on the spot. Even the writer ends up liking this guy too much for his own good. Too bad that Silver is a liar, conniver, and murderer.
Count Fosco, the polite, jocular, podgy, and harmless-looking arch-villain from Wilkie Collins' Victorian sensation novel, The Woman in White, is an early example of this trope.
Aornis Hades, villain of the second Thursday Next book, Lost in a Good Book, meets Thursday a few times and sees no reason why her plans to destroy Thursday's mind and everything she holds dear doesn't mean they can't be friends.
A literary example which is likely behind the character of Hannibal Lecter is Humbert Humbert, the handsome and erudite pedophile and narrator of Lolita.
Tom Ripley from The Talented Mr Ripley and other novels, while a Magnificent Bastard and Sociopathic Hero (in one book he tricks someone who snubbed him at a party into thinking he was terminally ill and manipulates him into committing assassinations for a mobster), is generally a friendly and cultured guy liked by most who meet him.
To those he deems worthy, Judge Holden of Cormac McCarthy's Blood Meridian is very polite, frequently engaging in thought-provoking philosophical discussion and, quite often, saving their lives in the midst of warfare through downright MacGyverish inventiveness. If he deems them worthless or should any stand in his way, however, he will mercilessly crush them. This ranges from the leaving one of his incapacitated companions behind to be slaughtered by pursuing enemies to scalping innocent Mexican civilians in the hopes of passing off their scalps as Indian. He also more than likely committed several acts of infanticide, and also possibly child molestation.
Gwendolyn Ingolffsen, the eponymous villainess of S. M. Stirling's Drakon, is quite nice and friendly for a member of a genetically-engineered master race who is attempting to reduce the whole human race of the parallel Earth she find herself stranded on to eternal slavery and degradation. She sees it as merely a necessary "taming" of "ferals". There are hints in the story (and others in the series) that she's actually quite mellow for a member of her species. In fact, all Draka are like this. As long as you accept that they're superior to you in every way and do what you're ordered to do, they'll treat you like a favourite pet. Cross them, though, and you'll end up with a four foot spike up you, as they point out to you how it didn't have to be like this, if only you'd obeyed without question. The ones who aren't like this end up in the Security Directorate. They'll stake a few of you at random just to show what you can expect.
Lord Bloodford, of Kingdom Rattus. He's extremely violent, half-crazy, and has a complete monster for a king, but still tries to hold himself to a higher standard. He actively disapproves of King Marrow's actions and plans for Marrow-Vinjia, but goes along because he feels he has no choice.
General Zaroff of The Most Dangerous Game forces protagonist Rainsford to participate in a hunting trip in which Rainsford is the prey after wining and dining him, giving him a night's stay in his lavish island mansion, and complimenting him on his book.
Dexter can be quite kind and considerate, devoting much time to gaining his girlfriend's children's trust and doing his best to keep his sister and coworkers at least not displeased with him. This sometimes puts a dent in his recreational activities, although his protective response to children can lead to his selection of "quality time" targets.
Grand Admiral Thrawn is almost terrifying because of this combined with his tactical genius. He's such an Affably Evil Magnificent Bastard that he reached the second-highest formal rank in the xenophobic Imperial Fleet despite being visibly alien. His troops revere him, and his enemies respect him. A single line in the novel Dark Force Rising, when a pregnant Leia despairs that he's going to succeed in his attempts to kidnap her, is what really makes his charming demeanor creepy.
"... who would smile, and speak politely, and take her children away." [emphasis added]
Thrawn's Watson and protégé, Captain Pellaeon, starts out this way before the Hand of Thrawn Duology, where he's a protagonist in his own right and really can't be called evil despite being the head of Imperial forces.
Professor Moriarty, archnemesis of Sherlock Holmes. Yes, he was the mastermind behind virtually every criminal activity in the whole of London. But he also behaved in a relatively curious fashion in "The Final Problem", when he and Holmes faced off. He was tracking Holmes and Watson up the mountain in Switzerland and could have attacked at any time; instead, he sent a fake messenger to lure Watson away from the place, as he had no intention of killing the doctor. He also, when he finally did confront Holmes, was polite enough to give him the time to write a farewell message for Watson to find when he came back. Upon learning that Holmes was on the verge of putting him away, his first response was to go to Holmes' lodgings and politely ask the detective to withdraw, as it'd be quite a shame to have to kill him to preserve his empire. This is continued in Moriarty's second appearance in the (much underrated) novel "The Valley of Fear", where an Inspector who meets him describes him as "a very respectable, learned, and talented sort of man", and states that "When he put his hand on my shoulder as we were parting, it was like a father's blessing before you go out into the cold, cruel world." Holmes couldn't help but chuckle at the irony.
The master healer Qyburn looks like "some child's favourite grandfather" and seems to be a genial and competent man in an otherwise psychotic band of mercenaries. It's later revealed that he is a Mad Doctor who was expelled from the ranks of the Citadel for performing vivisections on humans. In spite of his atrocities and work as a Torture Technician, he always seems to maintain a demure and professional demeanor.
The fandoms's favourite Magnificent Bastard, Petyr Baelish, A.K.A Littlefinger, Lord Paramount of the Riverlands, Lord Protector of the Vale of Arryn, Master of Coin and Lord of Harrenhal.
Roose Bolton, whose banner is a flayed man and lives in the Dreadfort, lives up to his family's reputation. Still, unlike his bastard son, he can be quite a nice man if you are not his enemy.
Aro is nothing but friendly and charming to Edward, Bella, and Alice, even going so far as to ask after Edward's father. But yet, he's a power-hungry maniac who attacks the Cullens unprovoked because he wants the talented members of the family to join his coven.
James. He wanted nothing more than to eat Bella but yet he was completely kind to her all throughout the torture session and always had a smile on his face.
The White Court is labeled as the most dangerous of the three vampire courts because many of them act like this. The rest are Faux Affably Evil, but are still quite skilled at being friendly and nonthreatening up until they rape you to death or kill you through sheer terror. In particular, Lara Raith is shown to be a genuinely civil and affable woman who tries to limit bloodshed and talk out her issues with others, before resorting to cat's paws to kill her competition in inordinately elegant manners. In Turn Coat, Lara hangs a great big lampshade on this. "A monster. A habitually neat, polite, civil, and efficient monster" as she's feeding wounded employees to her kin. One of the creepiest scenes in the whole series.
Marcone's a mob boss, responsible for much of the drug and sex trade in Chicago, along with various murders and the like, but he does have a highly developed sense of honor, and has helped pull Harry's ass out of the fire more than once. The heroes reluctantly admit that a united Chicago criminal underworld in Marcone's control tends to be less dangerous for bystanders (thanks to the Mob Bosses' Freudian Excuse) and sex workers. They still think he's scum, but know well there's worse humans out there.
He's the devil we know.
Aurora, the Summer Lady: kind, caring, friendly, and helpful to a rather angry Harry Dresden, right until she goes batshit insane. Played with: later books reveal that she was Brainwashed and Crazy as the result of possession by an Outsider.
Devi from The Name of the Wind is a polite, pleasant wizardess with an interest in literature. She is also a loan shark who collects the blood of her clients in order to perform unpleasant sympathy magic on them if they are delinquent in their payments.
Max Batu is a jolly, almost monk-like figure; he is polite, genuinely friendly, and the last person in the world to be suspected of murder. However, Max earns a living as a psychic assassin with the power of the Evil Eye, putting his victims through the most agonising pain of their lives before their deaths. On no account call the man a liar.
Clemael, the (self-employed) Angel of Mercy and protagonist of Hand of Mercy, is unrepentantly Fallen. But that doesn't stop him from being polite, concerned, and surprisingly tolerant of Helen's quirks, for most of the book.
From Jacqueline Carey's Kushiel's Legacy: the main villainess, Melisande Shahrizai, is evil through and through, but she is always smiling, calm, and collected. Not even engaging in Maniacal Laughter when it might be appropriate. She's intelligent, charming, very pleasant company, and will even give you a fabulous farewell party before killing you off.
Visser One deliberately invokes this trope, going for a Reasonable Authority Figure vibe as opposed to Visser Three's megalomaniacal tyranny. Keep in mind, though, this is reasonable by Yeerk standards — in other words, she'll still kill her underlings at the drop of a hat, she'll just maybe save them from their dying hosts if she's in the mood.
Joe Bob Fenestre from The Warning comes off as mild-mannered and polite for someone who's secretly a Serial Killer and Yeerk cannibal.
In one of the prequel books, Visser Three himself seemed to fit this when he was younger/in his earlier host body, prior to becoming an Evil Overlord.
Lucius Malfoy from the same series is a partial example. His tone is almost always even and coolly polite, but his words tend to range from mildly to extremely insulting to whoever he's talking to.
The entire Malfoy family is this, genuinely. While they do have an obvious superiority complex, they're genuinely nice to their friends and colleagues and really do care for each other. Lucius is also shown to treat Harry and his allies as credible foes, and all three members of the family consistently get cold feet at the idea of killing or torturing without reason.
Warrior Cats has Sol, who, although a bit self-centred, is seen as nice and polite by most cats who meet him...Until he starts playing mind games and manipulating them for fun.
Abraham Quest in Stephen Hunt's The Kingdom Beyond the Waves, so much so that for much of the book you're not sure if he's good or bad until he decides to destroy every sentient being on the planet who isn't a follower of his.
George Wickham in Pride and Prejudice. He is described as quite charming and "amiable", which causes both Elizabeth and Lydia to fall for him. It is only when Elizabeth finds out the truth from Darcy, that Wickham tried to seduce and then elope with his sister Georgiana in order to get access to Darcy's fortune without having to do a day's work, that his true character comes out. And then, Wickham runs off with Lydia, nearly ruining the Bennet family until Darcy pays him to marry her.
The insanely smart, educated, and incredibly cultured radio deejay, Jean-Loup Verdier, in I kill, with his highpowered knowledge of music, a voice that melts your socks, and a personality to woo women AND men. Switch off air and he's still cultured, highly intelligent, and oh so grammatically polite, but he kills and skins the faces off people to make his dead brother beautiful again. Still very polite, though.
In Lord Dunsany's The Charwoman's Shadow, the Evil Sorcerer is perfectly polite to the hero, even if he omits that, by asking for his shadow, he is effectively asking for his soul. He's even polite when describing how great magicians have high honor in Hell.
Yefim, the Mordovian gang enforcer in the Dennis Lehane novel Moonlight Mile, is quite friendly and jovial. Even when he's threatening Patrick Kenzie's wife and daughter.
Forgotten Realms: Jarlaxle, of R.A. Salvatore's The Legend of Drizzt novels. He won't hesitate to kill innocents, works for the highest bidder, doesn't seem to be inclined to turn down any sort of job, uses slave labour consisting of "lesser races", and once had a guy's face set on fire as a method of coercion. He manipulated events to start a war over the port of Luskan. After the fighting was over, with tons of citizens dead and the city partially destroyed, he made sure that food was scarce by preventing the flow of supplies into the city, and starved the people of Luskan until they were ready to rebel against the new establishment and install Jarlaxle's associate as the new ruler.
But he's almost always in a good mood (even when his life is in danger), is a clever Deadpan Snarker on those occasions when the situation doesn't visibly amuse him, has joined forces with Drizzt and his friends on more than one occasion, and and has saved Drizzt's life seemingly out of the goodness of his heart at least twice. Search this wiki for CMOAs and CMOFs associated with Jarlaxle. There are quite a few, because a lot of fans consider Jarlaxle both awesome and funny.
In other words, he's a mercenary-minded adventurer, but of the "sneaky bastard" type, rather than the "Blood Knight" type. Also, Luskan wasn't an innocent halflings' glade. It's (among other things) a major pirate nest with Arcane Brotherhood and Kraken Society jostling behind the High Captains' "throne". These behaved halfway decently only due to being bullied by Waterdhavian "superior firepower".
Cory Doctorow's For the Win contains a tale of a sweatshop manager who would take the poor workers out to theatres, buy them stuff, be their bestest friend - but always find some (seemingly sincere) excuse to avoid paying their wages. One day, he vanished with all the takings, never having paid a single rupee.
Captain Shannon from The First Casualty is the personification of what the corruption war can do to the human soul. He is convicted that his merits in combat and the horrors he experienced first-hand pardon him for every atrocity he commits, like raping indiscriminately or murdering a Warrior Poet who got disillusioned with the war and was about to come out with it. He maintains a nonchalant and amicable demeanour most of the time, and apparently is sincerely devoted to the cause of victory and is concerned with the morals of his comrades in arms, at that.
Mule from Isaac Asimov's Foundation series is a more suitable target for pity than anger: he's ugly, sterile, and physically weak, but is amiable enough to befriend the protagonists. Too bad he's a psychic bent on conquering the Galaxy.
Malazan Book of the Fallen has Bauchelain, who can calmly explain to the woman he's just raped why he should not have raped his manservant instead.
Crell Moset from the Star Trek Novel Verse, though in his case, it's a crippling need to be liked. He genuinely wants the subjects of his invasive medical experiments to appreciate him. He's not really cruel in the usual sense, he's just lacking in empathy, and believes his science takes priority. Not only does he take steps to try and make his victims feel at ease - including singing pleasant songs - but the closest he gets to threatening is childish pique when people won't let him perform his experiments. In the Star Trek: Voyager Relaunch, as part of a Continuity Nod to Star Trek: The Battle of Betazed, he seems to genuinely think that the Betazoids were selfish in the extreme for taking back their planet and disrupting his earlier work there.
The Overlord of the Redeemers in Star Trek: New Frontier. His entirely self-serving moral code allows him to justify anything he wishes, as it's all "the Will of Xant", to which he, humble as he is, is a mere servant. Affably Evil definitely applies, as, true to his self-image, he's pleasant, soft spoken, and comes across as entirely reasonable in his conversations with others. He's quite friendly, really, for a genocidal warlord.
Huffer is happy and friendly, and willing to cut deals with the enemy to solve things non-violently if he feels he can get something out of it.
Swoop just genuinely wants to be everyone's friend and hug and love everybody, and apologizes profusely whenever his orders involve nasty things like holding people hostage.
Ratchet is a cheerful Mad Doctor who loves to make strange modifications to people, because he thinks the modifications make them interesting and genuinely can't understand why nobody ever likes or wants his changes.
Big Daddy often plays Team Dad, and always has an elderly fatherly demeanor. He often lists the Evil Virtues that they should embody, and how fighting and rough-housing help team spirit, even chatting with Side-burn's about the latter's problems.
Belvedere Delaney from Bernard Cornwell's Starbuck Chronicles is a cultured and charming spy for the Northern States against the Confederacy (explicitly not because he thinks they're right, but because he believes they'll win). He is probably (in story) responsible for more deaths than anyone else (he caused the Battle of Antietam). He also caused the capture and torture of the protagonist on spying charges (he was innocent and was eventually released), and caused the abduction (and forced abortion) of Starbuck's love interest, although they are both unaware of his role and regard him as a friend.
The old Count Magpyr in Carpe Jugulum has excellent manners, keeps vampire-slaying props around his creepy old castle to give his prey a sporting chance, and holds no grudges over the actions of past vampire hunters - even the ones who did succeed in staking or decapitating him.
In Death: The murderer in Portrait In Death is this. He truly believes that he is doing mankind a great service by killing young innocent people. In fact, he truly seems like a Nice Guy, if you ignore the murdering part.
Gone: Caine is a perfectly pleasant, polite person, until you imply that he doesn't deserve to rule the world.
Lorthas, the Big Bad of the Boundary's Fall series, exhibits this trope, always ready with a smile, a polite word, and often enough with a bottle of wine to share. He does have dungeons, but when he finds out how The Dragon is treating the prisoners there, orders conditions improved.
The Leucrotta in The Orphan's Tales is actually a fairly nice guy, if you don't try to fight him. Even then, he'd mostly kill you because that's his role in the story, not because he actually dislikes you.
In Welcome to Dead House, the antagonists are friendly with the main characters except that they have to invite them over, especially Karen Somerset, who says she wants to be a nice person but everyone needs fresh blood to survive. Same with the TV version of Karen, who would actually be an Affably EvilAnti-Villain since she actually seemed reluctant to engage in the "feeding" that everyone in the town had to do to survive, repeatedly saying she wanted to be friends with Amanda and Josh.
In the Slappy series, outside of the fact that he wants to make preteen girls into slaves, he seems like a fun guy. He just likes to play pranks and tell mean (but true) jokes, allowing the audience to forget how dangerous he really is.
The creatures from The Beast Of The East just see it as an elaborate game and outside of that are quite friendly.
Della from The Curse Of Camp Cold Lake half the time was a normal kid outside of being a bloodthirsty ghost.
The plant clone father from Stay Out Of The Basement (more in the book than in the TV adaption) tried to be a good father even though he was ultimately out to turn everyone into plant clones, even comforting the kids when they worried about things.
Mrs. Maudsley in The Go-Between is kind enough to Leo even if she doesn't understand him. But her determination to see her daughter married into the aristocracy causes an awful lot of damage.
Tortall Universe: Emperor Ozorne in Emperor Mage varies between this trope and Faux Affably Evil, depending. He does genuinely love his birds, and really is glad that Daine could help them. For every other character, he's only playing nice.
Detective (ret.) Leonard "Sugar" Brimley in Robert Ferrigno's Scavenger Hunt could be your favorite uncle, much more interested in fishing than killing people, which he does nonetheless although he seems to genuinely regret in all but one case, who was a director of underage porn movies, so even the hero doesn't really see him as much of a loss