this is a much discussed topic. But Roy and Falco need to be modified further to become distinct characters, however I much agree with this idea.
Such possibilities are:
[COLLAPSE="Click to see"]Mario -> Dr. Mario
Neutral B would change the fireballs to his Megavitamins. The move stays the same, sans visible fire effect.
Luigi -> Mr. L
Just a set of costumes with the reversed L and the mask.
Peach -> Daisy
Voice clip swap, along with changes in the heart effects, replacing with flowery effects, Toad could be replaced with a flower counter, by shooting pollen instead of spores.
Bowser -> Dry Bowser
Different sound effects and slightly changed voice (with a echoing, ghostly effect), blue flames instead of red flames during neutral B, as well as a new Dry Giga Bowser.
For both Peach and Bowser, feature their wedding versions from Super Paper Mario.
Link -> Fierce Deity Link
The Final Smash's Triforce effect is replaced by a blue aura surrounding the enemy.
Link -> Dark Link
Deeper voice and a dark Triforce effect during Final Smash.
Ganondorf -> Toon Ganondorf
Would swap his voice to voice clips from his appearence in Wind Waker.
Toon Link -> Shadow Link / Dark Toon Link
See Link above.
Pit -> Dark Pit
Voice clip swap.
Ice Climbers -> Reverse lead
Not a costume, per se, but the option to play as Nana instead of Popo, without switching their colors.
Meta Knight -> Galacta Knight
Perhaps a voice swap, as well? Wouldn't be much different. On a side note, Dark Meta Knight could appear as one of the color swaps for Meta Knight.
Olimar -> Louie / President / Pikmin 3 captains
Obviously. Complete with possible voice swaps, as well.
Fox -> James McCloud
Another easy one. Add the sunglasses... and perhaps a different voice as well?
Capt. Falcon -> Blood Falcon
Replaces the falcon design in his helmet to a Blood Falcon's skull design. Color swaps would be the same as original Falcon, perhaps some voice samples would be replaced, such as taunts and Final Smash, to match the replacement of the Blue Falcon with the Blood Hawk.
Pikachu -> Female Pikachu
Adds the heart-shaped tail, in addition to more feminine accessories as color swaps.
Pokémon Trainer -> Female Trainer
Replace Red with Leaf.
Marth -> Alm, Sigrud, Celice, Leaf and Masked Marth
They are really similar to each another, so it would work.
Ike -> Lord Ike from PoR, Hero and Vanguard Ike from RD, Greil and Paris
Featuring all of his looks as well as relatives.
Roy -> Eliwood
Eliwood is Roy's father and has a very similar appearence, so why not?
Ness -> Ninten
To easily represent the original Mother. Could be complete with new voice as well.
Lucas -> Claus
Obviously, no?[/COLLAPSE]
And that's it for the characters already appearing in Smash. This would also work for potential newcomers such as Isaac from Golden Sun to offer a Matthew (his son) alternate.