If a Superman game was made as a sandbox, based on his days in "Smallville" (as the TV series goes, not what he WOULD have done) then it could work, with him finding his feet and developing his powers due to circumstances that push him to his current limit and force an "evolution" (inFamous style).
Or they could go with another Smallville based idea of the "Phantom Zone Escapees" thing and make it so he has to hunt down beasts that could actually kill him, while also fighting off Zod, Braniac and Doomsday.
I know some people don't like the TV Series, but it does have some good "potentially a game" ideas.