One of the most memorable video game villains for many people is Sephiroth from Final Fantasy VII. He killed Aeris (gasp, spoiler alert...) who was one of the playable party members, a sweet flower shop girl from the slums of the big city. By the end of the game, Sephiroth was trying to destroy the entire world by bringing a meteor down to earth, so he's definitely got the bad guy thing going on. However, despite all this, Cloud (the main player character) still remembers a time when Sephiroth was like a brother to him, saving his life on training missions when they were both soldiers together, and teaching him how to survive in what was basically a war zone. Because the story of the game is so closely tied to Cloud, the player sees this sympathetic version of Sephiroth and knows that at one time, he was kinder and gentler.
|This is Sephiroth doing what he does, burning villages and such.|
I think a big part of what makes these characters enjoyable is that their personalities are multi-faceted, so the viewer can relate to them in different ways. There's definitely a lesson to be learned here. Making one-dimensional bad guys is easy, but it'll be really hard to get anyone to care about them beyond wanting to see them splattered against a wall.