Sephiroth had quite a bit of character development in the Kalm flashback. He talks about not remembering a hometown, not having a family, how Dr Gast was his only father-figure and how he left. Sephiroth definitely came across as a very very lonely individual, stuck in the shell of a super-warrior. Then he comes across the Jenova project and his mind completely cracks.

Sephiroth's aura of invincibility is quite justified. His name is almost mentioned from the beginning of the game. And always as the greatest SOLDIER who ever lived. Then there comes the Shinra buildng where he (technically Jenova, although you don't know that at that stage) massacres the guards and the President. There's a huge build-up before you even know what he looks like. It kind of reminds me of Voldemort from Harry Potter, in that he is an invisible, malignant presence until much later in the book.

And Sephiroth's music is fairly epic. Definitely not the greatest song in the world (as some fanboys insist), but the entire composition gives an impression of an immensely powerful dark force. His look is also quite intimidating, especially when he walks through a WALL OF FIRE in Nibelheim. And he carries a six-foot long katana. That definitely suggests some serious power.

So I don't think Sephiroth's reputation comes from one single facet of the game, but as a combination of the whole. Kefka cannot compare merely because technology has created such an advantage for Sephiroth that he cannot overcome it. Although I don't understand how a character whose entire reason for wanting to destroy the world is because he is completely mad and therefore he can is deeper than someone who is a human experiment who has been lied to for his entire life. Oh, and who has the genetic make-up of an alien.