Very intriguing project you guys have going here. Curious: having any luck with the AI yet? And do you have alternative color schemes (or something along the lines) for multiple players selecting identical characters? Perhaps a prospective concept for the 1P story/adventure mode?
I would think some blend between SFA3's World Tour, KoF 2006's Quest Survival, FF's Countdown Mode, and SSMB's Adventure Modes would be great; just factor in some platforming sections and gimmicks that utilize players' moves in ways other than *just* combating other foes, perhaps add in some popular, simple dronelike enemies to populate them (and treasure/goodies/powerups to collect from said games), meant primarily to weaken the player or run them out of time; and top that off with a World Tour-style showdown.
Conclude that segment with the ability to buy back health, extra lives, more time, etc. between "chapters," followed by a choice between 2 or maybe 3 challenges at a time, for an entertaining, nonlinear kind of approach. I'd suggest at *least* 2-3 "final boss" stages, depending on routes you take to get there, too. The drone enemies could also spawn (or be triggered to spawn) in the regular game as well; allowing them to spice up the action a bit, or as a designed response to interfere with infinite attack loops.
Each character should ideally have at least 3 different, coinciding AI patterns; not too unlike the way Pac-Man ghosts work. Facing one alone isn't going to be too hard to the player, it's facing the
team of them that makes it challenging. Granted, each character will ideally play to their strengths, so a character with vertical-oriented attacks well tend to home in on players' x-axis, for instance; while keeping an advantageous degree of distance from the player.
One ideal example of a challenging AI team is one particularly offensive, in-your-face attack-oriented AI, another that homes in and uses items a lot, and a third that simply attempts to protect the other two; or attacks in proximity to, but not directly AT you - sort of confining your mobility, so to say.
You could also mix up the rules a bit - perhaps in one showdown, each of your opponents is given 30 lives, but they all die with one-hit-KO's. Maybe even a time-warp kind of tactic, where once you defeat one "life" and the second begins, it initiates a spawned replay of the first life; so now there's two sets of attacks to dodge.
Ideal fighter AI always comes down to a few key prioritized steps, however:
1. Defensive reactions (when not given an opening)
2. Homing in on ideal range.
3. Intial offense (the approach).
4. Finishing offense (the knockaway/juggle, and setting up a follow-up that buys some time to set the cycle back up at step 2, ideally).
Having a decent variety of tactics available to each character, and setting them up differently (yet indistiguishably) is a great way to keep players on their toes, so it's not like you're fighting a single AI drone, every time you play. Mixing tactics may seem like a good idea too, but then you're simply reducing the number of tactical approaches there are to face. And don't forget - while a multi-player game at it's core (4P), that doesn't mean you're limited to having that many active sprites/characters altogether.