So figure out who your villain is. What does she want? Why does she want it, and how far is she willing to go to get it? The villain who commits murder to further his plans isn't always willing to commit genocide, and knowing where your villain draws the line is important. What makes them unique, and no, that doesn't automatically translate to "what's their wacky Batman villain shtick?" It can be something as simple as a unique speech pattern or word choice that makes the character stand out. It can be a signature weapon or killing style, a modus operandi that is instantly identifiable. It must be distinctive, not needlessly flashy for the sake of flashiness.
What is an appropriate villain? It doesn't mean one that's well behaved and knows which fork to use for fish and which one is for salad. It means the villain is appropriate for the protagonist to confront and ultimately defeat, providing the player with a genuine feeling of well-earned triumph. A villain who's out of scale in either direction is a failure. Too small and the player gets no buzz from beating them; too big and the victory feels like a fluke or a deus ex machina. The same goes for the villain's style - make sure it matches the game's idiom and tone. If the game is realistic, the villain's approach shouldn't rely on blood, thunder and magic. If it's historical, keep the alien cyborg under wraps. If it's sci-fi, take advantage of that and come up with a villain who uses what your setting has to offer in terms of technology and alien races.
Ultimately, making a game villain is as much about structure and narrative design technique as it is about the villain itself. The best villain in the world won't play if the support mechanisms aren't in place to show off that villain to the best (worst?) advantage, and a hackneyed bad guy can get a tremendous boost from a supporting cast and good storytelling techniques. The one given is that you can't take a good villain for granted - or rely on your elaborate boss fight to fix everything. Instead, you need to do everything you can to make sure that your villain engages the player as a nemesis consistently and from the onset, doesn't frustrate the player in the process, and is around for a satisfying butt-kicking at the end.
Oh, and don't forget the "acting villainous" part. It helps.
Richard Dansky is the Central Clancy Writer for Ubisoft, the author of the novel Firefly Rain, and possibly the only person working in the videogame industry who has been published in Lovecraft Studies. His most recent game credit is Splinter Cell: Conviction. You can find him online at http://www.richarddansky.com.