I too would put Superman in fantasy instead of sci-fi. Sci-fi can have a big range in terms of hardness, but the key difference from fantasy is how it explains how things work.
Superman flies because -- I don't know how Superman flies. He just does. It is a convenient and ill-defined magic. It is part of a character used for story telling and the story is how he helps people in situations where no normal human being would be able to help, because that makes him a superhero. And he's practically invincible because that's convenient and also helps make him a good superhero, save for exposure to a made up substance because... (wait, why is Superman vulnerable to Kryptonite again?). Google, help me:
The prevailing theory in geekdom is that kryptonite can kill Superman because it disrupts his solar panel-like energy absorption.
That's the essence of fantasy right there. It left people to their own devices to try to explain why something in that universe works the way it does. Superman's powers might as well come from the same place as Thor's, or Sauron's.