I know the idea of costumes has been thrown around a lot, but I'm going to mention it again and make a list of characters that could have costumes and what they'd be for characters that are either already confirmed or should be.
MARIO
Dr. Mario (slower, but heavier and more powerful; Megavitamin replaces Fireball)
Baby Mario (much faster, but also lighter and a bit weaker; can float down using Cape after Up+B)
Paper Mario (lighter and slower, but with more useful moves and more powerful; can glide with Up+B as paper plane)
LINK
Young Link (see SSBM, assuming he's not going to return)
Shadow Link (same stats, but would still make a cool costume)
WW Link (assuming WW Link's not in the game... can't think of any non-visual differences as I've never played WW)
PIKACHU
Pichu (see SSBM)
Raichu (slower, but heavier and more powerful; Zap Cannon for a Smash B, but make it like Samus' Charge Shot)
Whatever the Pikachu-ripoff from D/P is (never played Pokemon D/P either)
FOX
Wolf (I seriously hope he gets put in the game... if not, make him a slower and more powerful Fox)
James (I have no idea for James' stats... perhaps faster but weaker?)
SAMUS
Dark Samus (never played a Metroid game apart from First Hunt ._.)
BOWSER
Bowser Jr. (faster, less powerful, paintbrush for Smash B and Shell Toss for B)
DONKEY KONG
DK Jr. (um... I really have no clue on this one)
YOSHI
Birdo (less speed & jump, more power & weight, Egg Spit for B, Up+B move w/ bigger height gain)
PEACH
Daisy (faster, less powerful, change Toad in B move to heart)
Pauline (same speed, less powerful special, more powerful physical, worse jump)
Rosetta (no idea)
WARIO
Classic Wario (change Wario Chopper to whatever the Charge is from WL4, no idea what else)
POKEMON TRAINER
Girl from FR/LG (visual change)
Rival/Gary (visual change)
Ash (getting a bit iffy... but still, visual change)
LUCAS
Ness (I really hope he's in Brawl... if not...)
SONIC (assuming none of these characters are in Brawl)
Shadow (oh come on, what else did you expect? Same speed, more powerful, lighter.)
Knuckles (slower, worse jump, slightly better special, WAY more powerful)
(subject to change)