In my mind, the thoughts of these two posts, in combination, identify and solve the problem. Once you find out (by reading any comic or watching any cartoon) that Superman is not 100% invincible, that is.
They can make you feel powerful and still have challenge. It all depends on what they want to use the character for. Just as Arkham Asylum gave Batman his own unique gameplay formula rather than aping another game and applying Batman to it, Superman needs to re-think how the Superhero game concept works specificially for Superman, rather than just trying to be Spider-Man except you fly instead of web sling.
The problem with a Superman game is that the makers of the game have to come up with antagonists that can hurt Supe consistently, and not just from the level bosses like Darkseid or Doomsdays. As Superman goes through a level, he can't just encounter kyptonite in every corner, and gamers won't suspend their belief if he gets hurt by street bums or muggers with guns. It's alot more complicated when you think about it, because Superman is so invincible the challenge is to create obstacles that he has to deal with and consistent with our image of the Man of Steel.
Traditional thinking leads to Raiden's problem... how can we get street level thugs to hurt superman? This has been the thinking in every superman game to date and it has been scarcely passable at best. Keep in mind, these street thugs shouldn't be able to hurt OR touch Spider-Man EITHER, but they do. It just looks sillier than when Spidey does it.
When you take Timstuff's suggestion, and design a game AROUND superman, you get the idea that Superman really is about those big boss battles, because those are the only ones that can hurt him, that really 'hurt' the city, per se. It's much better to take a more Shadow of the Collosus-styled approach, where Superman's 'missions' consist of 16 truly epic boss fights, some taking several rounds, and some recurring, rather than taking on thugs with Kryptonite guns. There's room for a little of that, of course, but containing Superman is not the point. Give him a large diverse overworld that's really just a battle arena and go to town.
Now when you're talking about a 60 foot Metallo, or an Armored Lex Luthor, or a tricked out Toy Man (that's where the goons with Kryptonite guns can come in), or, yes, Darkseid, you have room to really build something that tests Superman the same way the collosii tested the silent guy.
That's my take. Not necessarily quick time events, but there would be a certain scriptedness to it, a certain mix of skill and strategy that's expected, and not always that easy to come across. It's one thing to feel invincible, it's another thing to work hard to stand over a defeated 60 foot monster that leveled city blocks with ease. That's when you feel powerful.