Even now I cannot think of a way to make this work without de-powering him.
It's easy enough. Superman canonically holds back. He can fight normal human criminals and giant space robots easily. He just doesn't hit the former all that hard. The latter get punched across the horizon.
He is, of course, invincible barring extreme circumstances. So Superman just can't die from normal attacks at all. He might flinch at getting hit by an RPG, but he doesn't get hurt by it. If fact, he probably wants to tank the hits because a wild RPG in an urban environment is a problem. That would be amusing if only because it goes against normal gameplay tactics of avoiding enemy attacks. Superman wants to get hit so no one else does!
Being invincible doesn't mean he can't lose, of course. Bad guys get away, city takes damage, disaster happens despite Superman trying to stop it. And if you go one step further, you make it so Superman can't deal with all problems as there's always at least two happening at the same time, and you suddenly have one of the core dilemmas of Superman as a game. Superman cannot help everyone, so he has to choose. Do you stop the out of control train or stop a jewel heist in progress? You cannot do both.
Being Superman is about choice. It's why he has his Fortress of Solitude. For when Superman just needs to not choose for a while. He'll still show up if a giant monster or a huge meteor suddenly shows up, but otherwise he's taking time off.
I would probably make the whole looking for trouble thing a player initiated thing. Like using his Super Senses to find areas of interest, then having to choose one. How you choose would then determine the reputation you get as Superman. You know, there's a difference between a Superman who's often seen fighting crime and one that's often seen doing search and rescue. But both are a valid interpretation of Superman, it's just your Superman. Someone else's might be something else.
That is the AAA Superman game I want. Be Superman. Be the Superman you want to be.