My opinion is that even if you want to make a character deep, it's actions should still hit even if the player doesn't dig and stays at the surface. Making digging a requirement seems suicidal too me, chance is the player won't dig at all, especially if there's noting on the surface.

As for a villain specifically, other than making it hit on a basic level, try giving it a lot of style.

author=Crystalgate
My opinion is that even if you want to make a character deep, it's actions should still hit even if the player doesn't dig and stays at the surface. Making digging a requirement seems suicidal too me, chance is the player won't dig at all, especially if there's noting on the surface.

As for a villain specifically, other than making it hit on a basic level, try giving it a lot of style.

"Style" is awfully vague though; I feel like, as advice, this is basically on the level of "write them well." Trying to aim for "style" without a clear, concrete idea of something that will appeal to players, the results are usually cringe-worthy.

Not having owned a Zelda game since Link to the Past, I have nothing to say about Ganondorf, but-

For Sephiroth, I think that a major component of what made him work as a character was something that basically everyone adapting and reusing his character has failed to imitate. When Sephiroth has appeared in later works written by Square/Square-Enix, he tends to come off as a grandiose, Evil Is Hammy figure. But this really wasn't the case in his original incarnation. Sephiroth's character arc is that of someone who goes from being relatable and accessible to other people, to alien and inaccessible. He and Cloud share some significant history together, but this means much, much more to Cloud than to Sephiroth. Their rivalry is almost completely one-sided. Sephiroth is a villain who has personally, by his own hands, wrecked Cloud's life, and he doesn't care, because he hardly regards Cloud as a person at all; Cloud is just an incidental figure to him.

It's really not even a case of their past having lopsided, significance, a But For Me, It Was Tuesday situation. Cloud was there for some experiences that were formative to Sephiroth as well, but Sephiroth has basically stopped identifying with human beings. Sephiroth doesn't assign importance to Cloud for being there during some of the most important events of his life, any more than an ordinary person would assign importance to a bird for being present on an important occasion. It doesn't matter, it's just a bird.

(This also ties in to the central reveal of Cloud's character. Whereas most Final Fantasy protagonists find that they're prophesied heroes, or have some close personal connection to the antagonist which is meaningful to the antagonist as well, or are otherwise Chosen or special, Cloud's reveal is that he really isn't anyone special or important, except, like anyone else, on a personal level to a few people who know him.)

This, I think, is the significance of that final scripted battle between Cloud and Sephiroth at the very end of the game; it's not enough that Sephiroth be defeated, he must be brought down to a level where he can personally acknowledge the one defeating him.

Of course, while the conflict dynamic was interesting, it might not have meant much without all the length that the creators went to to characterize the Planet itself (the way that they constantly capitalize the word throughout the game is yet another measure to encourage you to think of it as a character in its own right.) Loads of villains have a goal of destroying the world, but very, very few games go to comparable pains to make you take the destruction of the world personally. For all that people joke today about the block-people graphics of Final Fantasy VII, the pre-rendered environmental graphics of the game, in many locations, still look really good today, and by the standards of the time were absolutely jaw-dropping. And over that, the writers developed a theme of exploring the Planet and humanity's place in it, and how we relate to our world.

These are the sort of considerations that made Sephiroth such a powerful figure in his original incarnation. Developers in later games trying to reduce those factors to "style" is, I think, why he's been so poorly copied in subsequent games.

In terms of making a character "deep," I think that what you should really be aiming for is to develop some kind of theme which will affect the player even if they never consciously notice and analyze it. The player doesn't have to notice that the writers of Final Fantasy VII were developing a theme of exploring humanity's relationship with the world they live in to be affected by it and feel a closer relationship to the setting of the game than they would to the settings of most other games.