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]