Mario, Luigi, and Peach would have the most epic costumes!
Tanooki suits, Tanooki tails, wing caps, rabbit ears, Hammer Bro, penguin, various paper mario costumes(not 2D), then you can go to the various color swaps like Galaxy's flying Mario or the Fire Suit.
Dk and Diddy don't have much outside of costumes from other Kongs like Cranky, Funky, Swanky etc.
The Zelda characters also have much to work with from the various installments over the years.
Then for characters that truly don't cut it for smash, a full on costume skin would be welcome as well. Daisy for peach, Classic DK for DK, etc. God I would love that. Even if each character recieved just one true costume swap that would make me happy. They did it with Wario, hopefully they up the progress with everyone else.
With all the talk of customization on the 3DS to show them off on the Wii U, I wouldn't be surprised if beyond full on costume changes, we can dress characters as we please. At least add to their original costumes, like just sticking a Tonooki tail on someones butt with a DK tie on their neck.