First off, I have to say that Brawl's greatest innovation is Solid Snake: each A and B button move with Snake activates a different weapon or item. It is really awesome to have such a massive amount of control over many different Snake weapons; no other character really has this level of variety and flexibility. If I want to play an entirely melee attack game, I can. Or I can do it entirely with explosives, or with two types of mines and artful dodging.
Second to Snake is the Pokemon Trainer (and Olimar to an extent). Each of the Pokemon have "moves" which are not just attacks that can be combined willy-nilly, but specific moves that come in handy in specific situations. I think this is what Smash was always meant to be, a strategic combination of moves, not just a beat-em-up that looked fancy and played easy. Those characters that melee only are really boring compared to the ones that have lots of awesome and varied abilities.
I honestly believe, with an honest and totally truthful heart, that they could make an awesome game based on the Pokemon Trainer. During the Subspace Emissary, the Pokemon trainer only has control over a single Pokemon, but as he meets up with other Pokemon he can add them to his roster by beating them in a fight. Unlike Pokemon proper, you have direct control over your Pokemon via Smash controls, and for some reason I still felt like I was playing Pokemon. It was rather awesome to be fighting Charizard with both Squirtle and Venusaur, and know that I was going to gain access to Charizard if I beat him.
My proposal: why not make a Pokemon game where you control your Pokemon in a fairly direct way, like in Smash? Use basic Smash controls, where each Pokemon controls the exact same way, but with different attacks. Slow the game down a tad bit, add some strategic elements to the already strategic Smash system, and I think you have a winner.