Most definitely Shodan. System Shock 2. Her alternating between kind and sympathetic to jarringly psychotic set me on edge. Shodan terrified me. She contributed, largely, to the atmosphere that made System Shock 2 so damn terrifying. She's hard to describe. They kind of tried the same approach with Fontaine from Bioshock, but it wasn't the same. He just came off as a thug, albeit a smart one. Shodan was brilliant. She plays you like a fiddle. She's a true sociopath, and you're the rat in her maze, running to and fro for her amusement. However, there are times when her psychosis breaks, just a bit. And that makes her all the more terrifying. You have no way out, and your only companion in this hell is The Red Queen on Acid and Steroids.
Otherwise, let's see...
Sarah Kerrigan, of course, from Starcraft. Such an amazing and tragic character. It's hard to fight her, knowing that deep inside the Queen of Blades is a good woman, and one that you get to know throughout the first game.
From Warcraft, Arthas Menethil. They say the road to hell is paved with good intentions, and no one embodies this like Arthas. He's a likable young ruler who genuinely cares about his people when we meet him, and his descent into madness is even worse in that it is you carrying out his atrocities. Stratholme... damn... Runners-up include Medivh and Garona.
GLaDOS, Portal. She's great. It's like Shodan, except instead of deeply psychopathic and absolutely terrifying, she's cracked, random, and still pretty scary. She's also one of the few schizophrenic, tyrannical computers that I kinda felt sorry for as I was killing her.
The Monolith/Chernobyl N.P.P./The Zone - S.T.A.L.K.E.R. You might not agree with a geographic area being considered a villain, but personally, I have never learned to fear and respect an enemy as much as I did The Zone and it's inhabitants. The Zone wants you dead, if it wants anything. Barely perceptible anomalies, radiation, packs of monsters, crazy cultists, a bad economy, scarce ammo... Nothing has stuck with me as much as moving through an anomaly-infested and radioactive garbage heap, praying that I didn't hit a heavy rad pocket, throwing screws ahead of myself to set off anomalies, all for the sake of finding one artifact to sell to get a rad suit. The Zone isn't an enemy that you fight, in the classic sense. It's a mutually abusive relationship. You learn to work with it, to use it, to exploit it. And in return, it tries to kill you. If Shodan weren't so good, this would be at the top of my list.
Added after:
I couldn't live with myself if I didn't include Hugh Darrow from Deus Ex: Human Revolution. I find myself favoring Sarif's philosophy the most, and I'm not a fan of Taggert. However, Darrow would not just control people. His method for terrifying people into banning augmentation is to control people, literally take control of their augs through a virus. He turns them against their friends and family, causes worldwide chaos, for no reason other than the fact that he disagreed with augmentation, and that he thought he was smarter and his opinion more important than everyone else. It wasn't that he didn't trust people to see the danger of augmentation. His narcissism led him to need to be the one who showed them. And so many people had to die to sate his neurosis.