First, I'd start by
having dialogue. Even if there's no voice acting, making all the characters literally mute was simply stupid.
Secondly, the structure of the game would change massively.
Whoever you pick at the start of the game (Mario, Kirby) determines whose path you follow afterwords. Picking Mario ends the first stage before the boss fight and defaults to Peach being chosen by Kirby, picking Kirby lets you choose which princess he takes and locks you onto Kirby's Story. After beating either, you unlock the other's story.
Following Mario's story gives you him and Pit and ends with the fight against Yoshi and Link over Zelda. Beating it unlocks Link's Story.
Following Kirby's story gives you him and the princess of your choice and ends with him joining Mario, Link, Yoshi, and Pit. Beating it unlocks Link's story.
Following Link's story gives you Yoshi and ends with the fight against Mario and Pit over Peach. Beating all three of them unlocks the Five Heroes' Story and the DK Story.
Beating the DK Story gives you Diddy, Fox, and Falco. It ends with the boss fight against Giant Diddy, and unlocks the Three Swordsmen's Story.
Beating the Three Swordsmen's Story gives you Marth, MK, and Ike. It ends with defeating Galleom and unlocks Lucas's Story.
Beating Lucas's Story gives you Lucas and all of Pokemon Trainer's pokemon. It ends with the fight against Galleom and unlocks the Halberd Story and the Bomb Factory Story.
Beating the Halberd Story gives you King Dedede, the Ice Climbers, Lucario, Snake, the princess you didn't choose, and Mr. Game & Watch. It begins with the otherwise cut events pertaining to King Dedede and the Halberd, ends with the recruitment of Mr. Game & Watch, and is one of the three keys to unlocking the Finale.
Beating the Bomb Factory Story gives you ZSS, Samus, Pikachu, Captain Falcon, Olimar, Donkey Kong, and ROB. It ends with the Bomb Factory's destruction and is the second key to unlocking the Finale.
Beating the Five Heroes' Story doesn't give you any more characters. It ends with the three groups meeting and is the third key to unlocking the finale.
Beating the finale gives you Bowser and Sonic (and *can* give you Ganondorf and Wario, provided you met the conditions for unlocking them). It ends with the defeat of Tabuu and unlocks Sonic's Story and Snake's Story. Getting all of the characters will also unlock the Villains' Story.
Beating Sonic's Story doesn't unlock any more characters. It ends with part of Sonic's world being engulfed by Subspace and Sonic choosing to enter of his own free will.
Beating Snake's Story will give you Wolf, Toon Link, and Jigglypuff, lulz. It ends with Snake (by himself) infiltrating the Halberd.
Beating the Villains' Story doesn't unlock any more characters. It ends with the villains abducting Palutena.
Beating all of the stories unlocks a dozen or so SSE stages for Multiplayer, Boss Battles 1, Boss Battles 2, and Boss Battles 3.
Beating any chapter unlocks its episodes.
As for major rewrites...
Five Heroes' Story: Bowser's troops take all of the trophies, rather than just the princess, which will always be the one you chose in Kirby's story. Near the end there will be a boss fight against Palutena, under the control of the Subspace Army.
The Halberd Story: Like I said, it starts off with a new stage specifically for King Dedede, which is shown entirely in flashback form.
Finale: Dedede, Ness, and Luigi start off in Bowser's castle, rather than Dedede's.
Sonic's Story: It starts with a traditional Sonic story beginning, with Robotnik up to something and Sonic and friends doing their best to stop him. It consists of two levels: Green Hill Zone and Egg Carrier. The enemies of the former consist entirely of Sonic enemies, while the latter features some of those and Subspace enemies. New bosses include e-101 Mark II and the Egg Dragoon.
Snake's Story: More of a joke, really. It consists of three VR missions which are otherwise identical to the stages you'd find Wolf, Jigglypuff, and Toon Link in normally. Each of them pairs you up with the character you'd find in them. At the end of it Snake is given the specifics that lead to him infiltrating the Halberd.
Villains' Story: It starts with Master Hand recruiting Ganondorf and Bowser for his purposes. New stages are Diamond City (enemies: Black Sugar Gang, Wario, and Captain Syrup piloting a new mech), Mothership (enemies: Space Pirates, Metroids, and Mecha "Iron Ted" Ridley), New Pork City (enemies: various Chimeras, Pig Army soldiers, and Porky), Isle of the Ancients (enemies: ROB army and ROB), and Underworld (enemies: Snakes, Grim Reapers/Mini Reapers, Eggplant Wizards, Centurions, and Palutena).
New Enemies:
-Gamma Clones
-The Robots from Sonic Unleashed*
-Monkey Robots
-Black Sugar Pirate
-Big Black Sugar Pirate
-Space Pirate (Red)
-Space Pirate (Black)
-Metroid
-Snakes
-Grim Reaper/Mini Reapers
-Eggplant Wizard
-Centurion
New Bosses:
-Palutena/**
-e-101 Mark II**
-Egg Dragoon**
-Captain Syrup**
-Mecha Ridley**
New Modes:
-Replay Story: Unlocked after beating Kirby's or Mario's stories. Allows you to replay any story you've beaten with any character or set of characters you've unlocked.
-Replay Episode: Unlocked after beating Kirby's or Mario's stories. Allows you to replay any episode from any story you've beaten with any character or set of characters you've unlocked.
-Boss Battles 1: Petey Piranha, Master Hand, Crazy Hand, Galleom, Ridley
-Boss Battles 2: Mecha Ridley, Meta-Ridley, e-101 Mark II, Captain Syrup, Duon
-Boss Battles 3: Rayquaza, Porky, Palutena, Egg Dragoon, Tabuu
Minor Changes:
-Each story has its own score counter, and your score does not carry over between repeats of that story. Getting the continue screen at any point during a story resets your score to zero.
-Your final score is equal to the scores of every completed story.
-Replayed episodes do not have a score counter.
-Boss Battles scoring is determined first by time, then by total score. You have a total of ten minutes to beat every boss, time does not replenish between fights, and continuing subtracts a minute from your remaining time and sets your score to zero. If it can't do the former, then you get a Game Over.
-Any achievements involving beating Boss Battles will only require you to do so for one of them, rather than all of them.
-Boss Battles Difficulty alters your recovery options. On Easy, you simply revert to 0% after every battle (up to 3996% healed). On Normal and Hard you have three "All-Star"*** Hearts (up to 2997% healed). On Very Hard you have two normal Hearts (up to 200% healed). On Intense you have three Maxim Tomatoes (up to 150% healed).
*Don't know the name of this enemy. It's the most recurring enemy, though.
**I have general ideas for how these bosses would fight, but this post is big enough as it is.