A worthy opponent

The video game universe is awash in heroes, but the noteworthy villains could likely be counted on two generous hands.  Often, the "main villain"--the hero's true adversary--feels more like an endnote than a palpable force in games.  Players rarely form a connection to their characters' ostensible opponent, most likely because they can recognize that the villain of the story is not their opponent.  Rather, villains are mostly MacGuffins--merely excuses to "go on the quest" or create a wake of corpses behind the titular character.

Villains who remain in the collective imagination of gamers are generally those who can be identified not only as the player character's adversary, but the player's own adversary.  The AI constructs SHODAN (System Shock 2) and GLADoS (Portal) plausibly fill the role of the player's true opponent--these characters appear to manipulate the environment and give the orders to lesser AIs in an attempt to prevent the player from reaching her goals.  These characters are identifiable as Worthy Opponents because they appear to have the same qualities of the player: goals, agency, and motivation.

Goals

Mutually exclusive goals create opponents.  Therefore, when designing a game, it is important not only to identify the goals of one player, but to also identify the goals of all his opponents.  Classic games such as chess simply pit two heroes against each other, though there are other game forms that assign at least one person a special role, such as King of the Hill or Four-Square, which have a separate rule set for one person, putting the player in competition with everyone else, and everyone else in competition with each other.

Computer gaming, of course, allows much more development of the number and depth of these specialized roles through artificial intelligence, as well as online gaming.  Computer games have the opportunity to not only put players in competition with each other, but games in competition with games.  After all, isn't the true villain the one who wants what you want, but doesn't have to follow the same rules?

Agency

While the assigning of nominal goals to AI characters is firmly established as a carry-over from film and literature conventions, games like System Shock 2 and Portal still refuse to give the villains a fighting chance to achieve their goals.  The idea that SHODAN or GLADoS are actually manipulating the environment is, of course, an illusion.  The level designers are your true opponents in these games.

A truly great villain must be given true agency.  For sports games and the like, this is a matter of course.  However, developers of action titles and RPG's seem to be unwilling to let go of a tightly scripted roller coaster ride.  This is a mistake.  The lack of opponent agency leads to a cardboard cut-out experience that lacks any emotional connection not only to the villain, but also to the player's character, who seems 2D by association.  People are defined by their enemies.

Motivation

While it can be easy to identify the goal inside the game, oftentimes it's just as important to identify the goal that led you to the game to begin with, which could be called your motivation.  Why do people decide to play games?  Is it because they have something to gain?  Or maybe they have something to lose.

Establishing why the villain is playing the game is important in creating that emotional connection.  A man who's hell-bent on destroying the world for no reason is less compelling than the man who risks destroying the world to protect his country from certain destruction.  If the player can assign an entrenched motivation driving her opponent's attacks against her, not only will the villain become a fleshed-out character, but the opponent will also gain the psychological strength of fighting a battle worth fighting.  The action will become more intense on a deeper level, and the closer the player gets to defeating the opponent, the more the player will fear the opponent--an increasingly desperate opponent with less and less to lose.

Ultimately, the key element to creating a great villain is giving him the power to win.  Legitimately win.  The villain must not be a passive character, waiting for Batman to make a mistake so he can laugh in his face during the "Retry?" screen.  The villain must be actively changing the game's environment to make victory more difficult for the player--analyzing the player's strategy and attempting to neutralize it.  When the player is defeated, the player should not say, "I lost," but rather, "The villain won."