I've mentioned it before, but I think you'd have to have him depowered from the first cutscene by one of his villains via Kryptonite. The rest of the game would be him playing chase to the villain(s) and slowly gaining his powers back as the Kryptonite effects wear off.
Definitely have to go into space and give us a some tough aliens for him to exchange fists with and give us a heat vision space battle blowing shyt up... Warworld, Apokolips, parademons, etc. On earth he could fight some giant robots made by the Toyman. The game needs to be treated like a summer blockbuster movie: big, dumb fun.
There's definitely some cool boss fights he could have if they go the Arkham route and throw tons of villains at him: Despero, Cyborg Superman, Mongul, armor suited Lex, Metallo, Maxima, Darkseid, Eradicator, Zod, Brainiac, Bizarro, Solomon Grundy, Conduit, Doomsday...
Brainiac and Darkseid should each get their own games as the main villain and Lex can be constantly plotting and hanging around like the Joker.