Frank Fontaine. Bioshock.

Kefka, Sephiroth, Wesker, Liquid Snake, Pyramid Head, Saren, Ganondorf, Bowser, Ares, Fontaine, Dracula. That's about it.

Perhaps it doesn't have to be completely but maybe just at the beginning of the game, perhaps Gannon gets betrayed and then put away so that Vaati becomes the main villian.  It's not like Gannon is immune to falling for being locked up or trapped.  It would be a cool surprise since you don't expect Vaati to be in the console games, but it could still be done in a way that Gannon keeps his dignity and remains the most powerful in the series.  I'm just tired of the cookie cutter go beat the big bad same old boss.  It needs variety and the best way to maximize the variety is to have a "completely" new villian/story plot.  But if you go as far as to create a whole new villian that has never been in the series then you miss an epic opportunity to cater to fans of the series to stir emotions, surprise, and anger.  Though anything can happen if done right.

I do understand that a lot of people wouldn't think they'd like it.  And if it wasn't done tastfully, then it wouldn't be successful.  That's why I didn't like the Twilight Princess plot, but still a lot of people did, so there you go

Alber Weskern!! It's sooooooo cool
Almost like me!!

Sephiroth, Luca Blight, Gannondorf, Ocelot, Genesis

Team Rocket... I can't think of anyone else for some reason... :S

Bowser, Kuja.

Vader.... or maybe Liquid Snake in LBP

Whelp Sephiroth vs Kefka Round 100

Yeah, nobody's brought this up so far.

Another villain I really like is

Ganondorf, Legend of Zelda series.

He's probably my favorite villain of all time in terms of slow development of his character and the sheer sense of menace that he exudes. There's no video game villain with his particular history of wickedness and change and bad-assery.