Assist Trophy: Toad

I think before Toad becomes a character, he needs to be an assist trophy. He could just jump up and down saying "(insert character here) the princess is in another castle" and used as a distraction.

Assist Trophy: Rush

 Mega Man's sidekick deserves some action, but not enough to be a character just yet. Mega Man should start out solo, then maybe add Rush later. Rush could do a variety of moves at you, from turning into various machines to shooting at you like a rocket.

Zelda Series Enemies

Skulltulas are a definite must

Octoroks appeared in Melee, and sure do earn a reappearance

Freezards would be a great addition. Obviously, they could freeze you.

Moblins would be fun. They've been in nearly every Zelda game to date.

Poes could whack you with their lights and occasionally dissapear

Those annoying as possible Keese would be a great enjoyment to beat the snot out of

Redeads appeared in Melee, but failed to appear in Brawl. They better change that

Deku Babbas? YES

There's many more Zelda  enemies. Hopefully Nintendo will use some of them.