First and foremost: OP fails for not giving an "all of the above and then some more" option.
Character variety isn't important to me in terms of which universe the character comes from: rather I care more about the uniqueness of the character itself and their specific traits. For example I don't mind the fact that the game has Batman, Bane, and the Joker. I DO mind that the game has Nightwing and Harley Quinn. I mean, what really makes Harley different from Joker in terms of skill set? The fact that she is female? I want unique powers and abilities, I don't care where the character comes from otherwise. Posion Ivy would have made a great character, fuck the people who cry about too many batman characters or that half the female roster is from the Batman universe. Batman is popular and female supervillians are less common and typically suck- that's life. My sentiment is that this is a fighting game before a DC comics game, and I realize that others feel otherwise and thats a totally cool and valid argument. Its fair for fanboys to demand as much variety from their DC comics video game as possible, but whats also fair is that most people still playing the game one or two years later don't give two shits whether or not half the roster is from the Batman universe.
Its like when people complain about too many X-men characters in the Marvel games, even though the X-men series caters itself perfectly to fighting games. In DC comics it seems like half the villains and a handful of the heroes can DO ANYTHING LOL I HAVE SUPER STRENGTH AND FLIGHT AND IM INVINCIBLE AND SMART AND OH YEAH I HEAL TOO, like when you pretend-fought with your brother when you were six. In the Marvel X-men series most characters have one specific and unique ability which (typically) isn't too overpowered and is visually exciting. Why, then, is X-23 in the game (mvc3)? Why not Gambit or Nightcrawler or Cyclops? Is it because x-23 is female? Likely, yes.
I feel exactly the opposite about the stage selection, though: Why are most of the stages from the game specifically from the Batman/Superman universe? Take away duplicate stages at different times of day and make it a pre-match option instead. It seriously wouldn't be hard at all to come up a stage for every character universe and would bring twice the visual variety.
Finally- more skins. Particularly free skins. Continue selling them in packs for a slight discount but also give the option to download them individually for a dollar each. Sell packs without a specific theme or character in mind.