there are more than enough DC villains that can match supes in raw power. So finding people for him to fight is not really the issue. The central thing to make this is work is that you need to make sure superman is larger than life.
he needs to have a good flight mechanic (and in a pinch, a good "adrenaline flight"). he'll need the ability to actually interact with the objects in game and manipulate them. (i.e. get thrown through a building, picking up the debris to hurl back at the enemy, etc) And the battles need to be almost a little dragon ball-ish in presentation. Superman can't just get gut punched and fall over, he needs to get smacked so hard it flies through a row of cars, and tears through a water main pipeline in the process.
If I had the budget, I would also do staged maps. one map for the city, one map for maybe say, space, one map for the watch tower, one map for atlantis, one map for apokoleps, etc. they don't have to be connected, but each map would have to be it's own city to really support the superman style action. granted, this means the dev costs would skyrocket if we want these done well. This is why I think Bruce Timm DCAU style graphics would work better for this sort of thing.