Baron Soontir Fel of the Star Wars Expanded Universe is a borderline case. He serves the Empire, and from his last name you'd expect him to fall from grace—indeed, it's not clear for a while where his loyalties lie. He defects from the Empire, partly out of disgust about what Ysanne Isard and s have turned the Empire into, and joins the Rogues, but there are various hints that he may or may not turn again. After the comics didn't end, he vanished, captured by Isard... and, as it turns out in the Hand of Thrawn duology, captured because Grand Admiral Thrawn wanted him. Thrawn showed him something, implied but never stated to be the oncoming Vong invasion, and Fel joined Thrawn's Empire, which wasn't part of Palpatine's Empire at all. Ultimately Fel is one of the good guys, just not the kind to wear New Republic colors.
Blackadder: The baby-eating Bishop of Bath and Wells, who drowns babies in the font and eats them in the vestry. He is a colossal pervert, and enjoys the more violent parts of his work far too much. Such as putting red-hot pokers up the backsides of people who can't pay back their debts.
Warhammer 40,000 has the Commisariat an organization made up of many different kinds of people, from those that shouldn't be feared, like Ciaphas Cain, to villains whose men would stop rebelling if he just stopped flogging them.
Count Dooku in the Star Wars prequel trilogy. The ostensible leader of the systems rebelling against the Galactic Republic leading their forces in the ensuing Civil War, he's also a Sith Lord, and Palpatine's latest minion.
The Count of Groundsoaking Blood. A large and imposing vampire who commands spiders, can summon spikes of rock from the ground, can create flying swords and has come back from total annihilation about three times (depending on whether you consider the Mega Man Battle Network crossovers canon).
Some fans call into question Doctor Doom's academic credentials since he was kicked out of State University after the accident that disfigured his face. Still, as ruler of Latveria he presumably had time to finish his thesis at Doomstadt University or have them award him an honorary one...
Doctor Cyber, Doctor Death, Doctor Destiny, Doctor Light, Doctor Moon, Doctor No-Face, Doctor Phosphorus, Doctor Psycho... DC seems to like this.
Then again ... there's been a few times when The Doctor has kindly suggested that the Monster of the Week run away. And in-universe he's made the living incarnations of Space Nazi hate-hate-hate flinch. With words. Or as the Eleventh Doctor put it when facing down alien of the week . "Hello, I'm the Doctor. Basically, run". They wisely did. Though this trope only applies if you are evil, otherwise The Doctor falls under Names to Trust Immediately.
In "A Good Man Goes to War," The Doctor finds out this reputation is slowly changing the meaning of his name across time from "healer" to "warrior."
The Doctor: Imagine you were dying. Imagine you were afraid and a long way from home in terrible pain. Just when you thought it couldn't get worse, you looked up and saw the face of the Devil himself. Hello, Dalek.
While Team Fortress 2's Medic is a boon to his team-mates, his background ("From Stuttgart, at a time when the Hippocratic Oath was downgraded to a Hippocratic suggestion") and lines ("Ze hurting is more rewarding than ze healing!") suggest he's no more kind-hearted than them.
"Doctor Loboto" from Psychonauts likes to extract children's brains, the name an allusion to lobotomies (which would be the destruction of part of said brains, which is almost as creepy as what he does with them).
Tortall Universe: Duke Roger of Conte, so terrifyingly powerful a sorcerer no one in Tortall would dare face him except a DeterminatorAction Girl protecting her prince—and he even orchestrates his return from the dead.
The title "Fuhrer" (leader, guide) has been taken out of the German lexicon* Except for such constructions as Reisefuehrer (meaning, roughly "travel guidebook." due to... you know who. No self-respecting German leader would dare allow the word to be applied to them these days. Any title that would have used the word prior to 1946 now uses the word Leiter in its place. A character with this title in any modern work is almost certainly a Nazi.
Anime And Manga
Fuhrer King Bradley from Fullmetal Alchemist, though calling himself "Fuhrer" sort of comes off as a silly use of Godwin's Law. And oddly, "King" is his first name, not part of his title.
There's Hitler himself of course, but stylizing themselves as some variant of "leader" was very popular with the Fascist collaborators in the countries Germany occupied during the war. Vidkun Quisling, the puppet ruler of Norway, even used the closest Norwegian cognate, Fører.
Judge Doom from Who Framed Roger Rabbit. A Hanging Judge of the highest order, his stated goal is to create order in the toon anarchy, and the only way to make them respect the law is to execute all transgressors with his self-designed toon killing liquid, the Dip.
Judge Holden (more commonly referred to as "the judge") of Cormac McCarthy's Blood Meridian. The man easily ranks as one of the most violent and fundamentally evil murderers in the history of fiction. A giant, albino and utterly hairless murderer, the judge incites a mob to hang an innocent preacher under false pretenses, is a pedophile and rapes and murders many children, leashes and subjugates a mentally disabled man as though he were a dog and scalps countless Native Americans. Not only is he utterly without morals, the judge is also an incredibly intelligent, Omnidisciplinary Scientist and strong enough to wield a mounted howitzer as most men would a shotgun. In the novel's final pages it is implied that the judge is less a man and more an immortal force of nature and warfare—a god of violence and depravity, if you will.
In Star Wars, the Dark Lords of the Sith. Sometimes, this title even makes its way into conversation. (Lord Vader, Lord Sidious, etc.)
From The Cabin in the Woods comes Fornicus, Lord of Bondage and Pain. He's a Cenobite, so he lives to satiate his victims' desires by bringing them new "pleasures", eternal torture.
The Lord Marshal of the Necromongers in The Chronicles of Riddick, who leads his Religion of Evil on their campaign of annihilating inhabited worlds and enslaving those who can witstand their conversion process.
Captain, Commander and high ranks are good too, either for villains but more so for antiheroes (or just straight up good-guy heroes). Anything lower tends to lack oomph. After all, nobody's scared of a Private. Sergeants, on the hand...Anime and Manga
The GreatHouses in Faction Paradox. Bonus points for their home planet simply being called the Homeworld, due to it more deserving of the name than whatever planet anyone who argued was on. They're such a humble people.
The Lord of the Rings also has the Witch-King of Angmar, the undead warrior who leads Dark Lord Sauron's evil armies and tries to find his master's ring.