Dragon Quest VIII, which I just completed, does a good job of utilizing its main villain. From the outset of the game, it is made clear that hunting down the evil jester Dhoulmagus is the party's main goal. He first appears in a flash-back sequence, but quickly appears in front of the heroes himself, performing all of his evil deeds right before their eyes (and dropping hints to the player as to his real goal). About halfway through the game, the player finally gets the chance to fight Dhoulmagus directly. And yet, that is just the beginning. The heroes battle against the true villain of the game in three more major boss battles before the player even gets to the final dungeon. By the time of the second fight against the main villain, he had even started to recognize the heroes, and knew that he had to be cautious when fighting them. It created a wonderful sense that it was an ongoing battle directly between the main heroes and the villain.
Perhaps the all-time greatest console RPG villain is another evil clown: Kefka, from Final Fantasy VI. From the very first part of the game, where Kefka can be seen placing the Slave Crown on Terra's head, he has an almost constant presence in the game. He first appears to the heroes in person threatening King Edgar, lighting Figaro castle on fire, and sending a pair of Magi-Tech armor to kill the heroes, all the while filling the game with his insane personality. Whenever he appears, he does so by making his distinct evil laugh. He commits evil deeds across the entire length of the game, usually right before the heroes' eyes. He is rarely gone from the action for long, and appears in at least three boss fights in the first half of the game.
What made Kefka so interesting was not just his evil deeds and character design alone, it was the way he could be interacted with by the player. He doesn't just appear in cut-scenes to taunt the heroes, he is part of the game-play. When Kefka first appears in Figaro castle, he just stands around and can be talked to like any other NPC. During the chase scene before the poisoning of Doma Castle, he runs around the imperial camp, and the player has to actively chase him down and even fight him a couple of times. During a visit to the Imperial capital, the player can listen to him rant as he stews in a jail cell. These interactions make Kefka a vital part of the game experience, as opposed to just a character in the game's story.
For an action game villain, a great example is Virgil from Devil May Cry 3. Virgil appears as a major boss at the end of all three major sections of the game. Beyond that, he appears in half of the game's cut scenes. While his personality and design are obviously a big part of his success, his strong presence in the game is a big part of his success as a villain.
In contrast, the worst villains in videogames are usually the ones who don't even appear until the very end of a game. In Final Fantasy IV for example, the player doesn't even hear the name of the real villain, Zemus, until the second to last dungeon of the game. He only appears in front of the heroes two minutes before the final battle. Because of this, Zemus has never been a very popular villain. He never even had the chance to be seen as the game's real villain.