Video games, more so than any other form of media, allows a person to feel a connection to the characters in the story. Sephiroth may not be the greatest villain ever created, but he was "real." All his life he was raised a SOLDIER and taught to life his life in a specific was, some could say he was brainwashed, until he finally found out the truth, causing him to finally snap. As for his "2-Dness," as confirmed by the FF7 Ultimania Omega, there is very little actual screen time with the real Sephiroth, he may be controlling Jenova, who took on his form, but Jenova IS a 2-D character, meant to be nothing more than a pure animal that only exists to kill(much like Kefka).
In my opinion, the fact that Kefka was able to kill so many people is not a testament to how great Kefka is, but rather the to the shortcomings of the heroes who couldn't stop him. If Sephiroth were given the same chance, he would not have left the world in a state in which it could recover.
Finally, character deaths do amazing things for a story. It gives the player the same sense of desperation and hopelessness that the character must be feeling; that you are not an invincible team that has no possible way of loosing. As it has been said to death, the death of a million strangers could never feel the same as the death of a friend. Aeris' death was so significant because she was the first true video game friend to die.
*looks at his wall of text*
ehh, might as well stop here
