Plusle & Minun as a tag-team pair, a la Ice Climbers. The remaining member of the pair would cause damage to themselves with electric attacks when left alone, like Pichu did.
Captain Olimar, with Pikmin as additional attackers to add weight to his A-attacks. Again, like Ice Climbers.
Bowser Jr. Uses his paintbrush for B-attacks, and can transform himself into a "Shadow" version of other characters to imitate their non-B characteristics: A-attacks, weight, jumping height, etc.
Ridley. Dark Samus. Fusion Suit Samus. Mother Brain. Whoever, I don't !@#$% care, I want more Metroid characters.
WW Link and Tetra. Hey, maybe as a duo. That'd be goddamn cute. And way to choose between Link and Tetra as your primary... they'd behave like a chibi Link and Zelda/Shiek respectively.
Also, some more goddamn references to BOTH of the two generations of games that occured since Melee and before Brawl, not just the most recent one.