If you're going into a beat em up expecting earth shattering plots I think you're looking in the wrong place though. Final Fight is lauded as one of the best beat em ups of all time, and the plot to that game, in its entirety, is: a gang kidnapped the daughter of the mayor of metro city, and only a ninja, the wrestler/mayor, and her street fighting boyfriend can save her. That's the whole thing.
I think a lot of what makes some of the older beat em ups really work, even to the point of being fun today, is variety of moves. There are so many that people love, that I've personally never understood, because your characters are capable of doing like 3 different things. A normal button mashing combo attack, usually some kind of jumping attack, and maybe a throw if you're lucky. For me the ones that always really worked were the ones where you could do a ton of different things, so that you could mix it up and enjoy some variety, or even, if you were really lucky, be able to apply different moves to different situations based on what was most effective. That's where I think Superman shines. Each character has 4 different grapples, a couple of which can be used to destroy the environment and sometimes find hidden items, a projectile, several different button mash combos, a health draining special move, a couple different aerial attacks, and the ability to use Superman's strength to lift big things like dumpsters over their heads and throw them. There are certainly beat em ups that are far superior for so many reasons, but even within it's genre, within its particular platform, I think the worst game ever it is not.
I mean SNES also offered beat em up gems like these too:
Last Action Hero
Captain America and the Avengers
There's just no comparison.