Okay, this was actually meant to be put in another thread asking what franchises could be represented by one more character, but I took so long to type it that the thread was closed before I submitted it. But, it took me so freaking long that I had to put it somewhere. Here goes:
Mario:
Paper Mario. He's a completely different character with the same name. He would have G & W's attributes as a 2D character, making him super light, and he'd only face frontwards. His moves wouldn't even resemble Mario's, as they would have three RPGs-worth of choices for moves. He'd represent a high-selling and popular franchise spanning the N64, GCN, and Wii, and I wouldn't even actually group him with the Mario universe, really.
Legend of Zelda:
Midna + Wolf Link: Brand new moveset that would be completely off the wall from everyone else, and she represents a fresh face in the Zelda franchise, while Link, Zelda and Ganon are staples.
OR
And Majora's Mask Link, whose down B would transform him into Deku, Goron, or Zora Link. Zora would use his fin boomerangs, be a high jumper and medium weight. Goron would be a powerful heavyweight with a spindash like Sonic's or Jiggs' that can charge, and if given enough time, spikes would form and make him able to change direction, otherwise it's just a straightforward roll. Deku would be the light one, weaker but he could glide with his flowers, spit Deku nuts and use that snot bubble thing as a charged B. Young Link would then have Link's moveset, except his bombs would be changed to forward B, and Toon Link could be "Windwakerized". Smaller Link lovers get this character, Toon Link "clone" haters get a new, different Toon Link. Everyone's happy. (Oh, and his FS? Fierce fvcking Diety Mask. So awesome.)
Metroid:
Dark Samus. Ridley works better as a boss, and being a playable character wouldn't do him justice, really. Dark Samus's only move that would resemble Samus's would be a charge beam, standard B. Everything else would be phazon-based attacks, not missiles or bombs. She would be lighter and glide across the ground like Mewtwo, and also be able to glide as a recovery, much like Peach. She would look like Samus, but play nothing like her, plus not be able to turn into a hot ZSDS. Her FS could either be a huge Phazon eruption, or a Phazon Corruption type-move where she starts sparking with bright blue like mad and goes around Supersonic style, or turn back into Metroid Prime and take up half the stage killing things like a Giga Bowser. Lots of possibilities.
F-Zero:
Black Shadow. Main villain for a franchise represented by only one character three games in a row. That's just unfair. Plus, he would indirectly help the Zelda franchise. He'd be the Melee Ganondorf, a bigger, badder, but slower, version of Falcon- not a *complete* clone, but close to that style. Then Ganondorf can receive a brand new moveset, thus both parties are happy.
Starfox:
The obvious one, Krystal. She'd be the only Starfox character not to have similar looking moves, but rather, use her staff, which has already created moves perfect for smash bros. special attacks (a long range blast, ice attack, earthquake, rocket boost thing, etc.) Her staff would also give her very different A attacks, and would make her different than any other character, as she's the only one with that weapon choice. Then, her FS would be climbing onto a Cloudrunner and firing fireballs like in the beginning or Starfox Adventures, either Yoshi style or Snake style. Plus, all the yiffers can jerk it to her instead of ZSS. So many choices for sex appeal in a Nintendo game? Impossible!
Pokemon:
I WANT to say Mewtwo, but... the reason he was cut was simply because there were too many R/B/Y generation pokemon already- in fact, that's ALL there was. He was cut to give way to the D/P generation. So, I would add a character to represent somewhere in between. G/S/C was even before Melee's time, so that narrows it down someone from the R/S/E generation. Who better than one of the "forbidden seven"? Plusle and Minun. They would work like the Ice Climbers and use baby pokemon moves incorporated with Pichu's moveset, plus have his weight and abilities and such. Thus, Pichu lives on and another game is represented.
R.I.P. Mewtwo. It's okay, you're still the best, and you could dissentagrate all of these inferior pokemon before someone could say "Falcon PAAAANCH!!" Super Smash Bros. just can't do you justice because of your sheer awesome power, much like Ridley. But, could it have been so hard to incorporate you as a boss in SSE too? You were already the bad guy in, what, two Pokemon movies? Psssh. Mewtwo haters. Just kill them with your telekenesis and call it a day.
Donkey Kong:
King K. Rool. He's the obvious choice, even though any of the DK64 kongs or Dixie make good candidates as well. Brawl is still lacking in baddies, and he's a classic one. He'd add to the heavyweight class as well, and with so many different costumes and moves used in every game he's been in, there are a lot of potential moves to choose from. Classic, different, and adding to two still lacking groups. Perfecto.
Finally, my own 'wtf' character, because R.O.B. and G&W deserve another friend:
The Nintendo 64 Kid. Yes, him. He would have his classic pajamas, with different colors and patterns for costume changes. He could punch in the air screaming "YES!!" and ground pound like he did on that poor box. His shrill scream as he destroys his vocal chords could paralyze opponents nearby, then he could beat the **** out of them while having that bone-chilling expression as he screams "FOOOOUUUURRRRR!!!!!" Then, as a comical down B, he unwraps his remote control car and immediately become uninterested, thus creating a projectile to spam at opponents like ZSS's armor. He's such a perfect candidate for the 'wtf' character, a nostalgic representative of the N64 days, and a rep. for the Youtube generation of today. His legacy would go down in history as a part of this game, and he would immediately be a fan favorite just to hear those blessed words: "NINTENDO SIXTY-FOOOOOOOUUUUUURRR!!!!!" screamed over and over again until his poor little lungs burst. This may be a bold prediction, but I honestly believe he has the potential to replace Captain Falcon as the catchphrase master.