Personally I prefer the more "casual friendly" approach of Brawl, but as a compromise, I'd have mechanics like tripping and Final Smashes be able to be flipped on an off, like Items can be. You could maybe also have similar flip switches for the more advanced techniques Melee fans wanted to be in Brawl. I have no idea if that's possible, by the way.
As for characters, I'd like to see some of the Final Fantasy/Chrono Trigger characters that originated on Nintendo consoles, if they could work out the licenses with Square. Characters like Frog and Sabin. Also, it might be cool to have an Advance Wars character (technically Second Party, I guess?).
Maybe they could have the ability to summon Advance Wars units for attacks? Like the Mech unit's Bazooka, a jump like Snake's where they grab onto a helicopter?, a dash where they jump into a recon truck? A Final Smash where they call in a Bomber? I dunno if it'd work potential animation and balance issues I suppose, but I think it'd be really cool to see.
Also, Ace Attorney assist characters. Nintendo could probably wrangle that from Capcom, unless there's some kind of contract issue thanks to Wright being in UMvC3.
Ooh! Sissel from Ghost Trick! He could uh...possess objects? That suddenly appear on the battlefield? He dashes by possessing a basketball on the floor, and his Dash attack is the ball jumping off the ground to hit people? Again, animation and balance issues might make it too difficult.
I do love those really atypical designs in fighting games where characters work in a unique way from the rest of the cast. Like Pokemon Trainer and Olimar & Pikmin. I'd like to see more things like that.
