Interesting. I think they were on the right path, a lot of emphasis on the boss characters, the only things that can/should provide Superman with a real challenge. Luthor looks sweet. Even Kalibak looks hardcore, and he's a clown and a jobber, usually.
I think that paradigm is/could be very cool for Superman. For a character who's power is a main selling point, having him fight a bunch of thugs, even ones with kryptonite/magic/superlasers/macguffins kinda deflates the concept, like having Batman in a world that's impervious to Detective Vision.
That, coupled with their envirodestruction to show power, pretty much tells me they were spot on, and possibly ahead of their time. I think whoever goes after this next should basically pick up where they left off. 
To comment on the rest of the thread, it has to be free roam ala the Arkham Franchise because part of the selling point is the character's mobility. If Batman has nowhere to grapple and glide to, you miss a huge part of the character, if Superman has nowhere to fly to... why bother? The truth is, though, you can't fill free roam with activity, but honestly, with fights of truly epic proportion, do you need to? Superman taking out thugs or rescuing a civillian is about as easy as Batman finding a Riddler clue. not a challenge in itself, just a fun side activity to help you feel more like the character. Superman's main challenges are keeping people alive during fights and fighting impossibly powerful creatures. Kinda like Goku, in a way, actually. Speaking of, Superman v Doomsday would indeed be a great fight, but imagine if ALL the fights were like that, drag out epics that take down city blocks? Very cool, eh?
I think that's what Factor 5 was going for, and it's probably the best way to make a game that is fun, challenge AND superman-like.