FREE-FOR-ALL A new game mode: 4 or so people, who don't have teams. So teamless carnage, basically.
IDEA FOR NETWORK GAME CHAR SELECTION Instead of everyone selecting a character from their own roster, everyone picks their characters from the game owner's roster, and everyone sees only characters that everyone has. For example: Let's say that The Game Owner's roster is Ryu, Ken, and ULTRA RARE GUY. Player 2 Comes in, and he has Ryu, Ken and ULTRA RARE GUY in his roster also, so he and the Game Owner can select everyone. But then Player 3 comes in. He has only Ryu and Ken, so ULTRA RARE GUY is taken off the roster. Simple. Also, the owner of the game can set some characters to not be available in multiplayer, thus making cheating usable only if the owner wants it.
STAGE INTROS In some games, stages have intros. What I mean, for example In SNK vs Capcom Chaos, the first thing you see when you get into a fight, is the top of the stage, and text that tells you the stages name and the time when the fight happens. Other stage introes would be like this: A stage that's in some kind of crowded place, the stage intro would be people getting out of the way, showing the fighters, and the fighters do their intro poses and the fight starts etc.
SPECIAL STAGE... THINGIES I didn't know what to call em' Anyhoo, what I mean by this is stuff like having the floor be all ice, thus causing a slippery effect or having the stage be underwater/on something that hurts, causing all characters to gradually take damage. And stuff like that.