I like "Evil Paladin" types. Honorable warrior-types, but just believe the strong have the right (and responsibility) to rule the weak. Ashram, the Black Knight from Lodoss Wars, comes to mind, or an evil Rommel (or even like the Desert Fox, maybe a good guy fighting for the bad guys' side, due to loyalty to country or the evil king's not-as-evil father or some such)
After that, evil megalomaniacal (maybe gods themselves) chessmaster-type villains. Emperor Palpatine, the god Bane, the Joker, Marvel's Apocalypse, etc. They often plan for years, decades, or centuries, and, when the PCs start to uncover the plot, not only is it at the almost-too-late point, but they can't believe how deep that particular rabbit-hole goes. (or, like Palpatine, the PCs come about after the villain has already ostensibly won)