My problem with the Story Mode isn't that anything happens (or that Superman is the cure-all magic bullet for every situation).
I wish the game had down two things: Slow down and let these big events sink in, and give the other characters something to do.
Story Mode is a great way to teach people how to play the game by forcing them to use certain characters... yet they only use roughly 1/3rd of the roster. You can't tell me it wouldn't have worked or been enjoyable to play as Nightwing, or Raven, or Catwoman, or Harley Quinn, and go through their personal, emotional journeys. But we don't. We get lip-service to things they did or felt but no exploration and no ability to play as them.
And, on that "emotional journey", the game never pauses to let the actions of the game sink in with anyone. Flash eventually has enough (though he waits until Superman does something like MURDER A CHILD before deciding this isn't right), but he never dwells on this after jumping ship. We never see Wonder Woman question her decisions, never see Green Lantern explore why he allied with his hated nemesis, why these heroes seem so okay working alongside convicts and criminals, why their morality is all screwed up... or even why Green Arrow's heroic death didn't shake any of them to stand up before this point. These "alternate" heroes are all insanely weak-willed compared to the "proper" versions of themselves... and its to the detriment of the story. The game tries to make it black and white, but it's not; it's freedom versus security, Kingdom Come-level questions raised, and very few answers or exploration given.
And don't tell me it couldn't be done. Mortal Kombat 9 is a fighting game by them too, and it still took the time to explore and mourn the death of characters like Kung Lao, deal with the emotional fallout of disfigurement, loss of faith, and desperation in the face of annihilation, and it did it largely through effective means. You came to understand these characters, understand their personal demons, and empathize with them.
Just because people know Superman or Green Lantern doesn't mean they "know" them as people and not costumes. We could've really used more exploration for those without a thorough knowledge of the comics... like I wonder how many people knew that Shazam (officially "Shazam" now, not Captain Marvel) is actually a 10 year old boy in the body of an adult? That makes his hero-worship of Superman, and his fate in the game, jaw-droppingly shocking, tragic, and poignant, yet the game doesn't explain this or explore this.
Oh well, it could've been, should've been... but it is what it is: a backdrop to fighting. It's still better than 99% of fighting game stories, but it's still a lot of missed potential.