I can think of quite a few costumes, keeping to the theme of 'same character only'. By character:
Mario: Pretty much full. Don't touch him.
Luigi:
Dr. Luigi would be nice. I could live without the pills as well, as the different trajectory would be really odd.
Princess Peach: The
sports outfits would fit in nicely with that F-Smash of hers.
Nurse Peach from the Dr. Mario series would also be a nice nod. Also, since we've already got a Paper Mario reference with the Shadow Queen outfit...
Bride Peach?
Bowser:
Meowser. Please, for the love of god, give it to me. I need it.
Donkey Kong: His
Strikers outfit is really intense and stands out very well, and the only real outfit I can think of.
Diddy Kong: His
Strikers outfit is the only alternate costume I can really think of period.
Yoshi: Another case of having no real outfits to speak of. But there's always
Strikers.
Wario: I don't think he has any free slots, so we can pass on him.
Link: There's the alternate tunics on Twilight Princess Link, but I'm not sure how well they would fit in. Hmm.
Princess Zelda: Melee Zelda perhaps? To fit in with Link?
Sheik: See above.
Ganondorf: See above. (Also, purple Ganondorf when)
Toon Link:
Conductor Link comes to mind immidiately. I also wouldn't mind a Young Link-inspired outfit.
Samus Aran: There's so many suits that Samus wears, it's not even funny. I'm partial to the
Light Suit myself.
Zero Suit Samus: I can't think of any particular costumes, but the alternate colors of this suit are absolutely disgusting. I would like to see them changed.
Pit:
Sacred Treasure Pit seems to be the go-to response for everyone, including myself. I'd also like to see Pit's alternate colors cleaned up a bit, but that's just me.
Ice Climbers: I've got nothing, honestly.
R.O.B.: The inclusion of Virtual Boy R.O.B. has made me want to see
Tocksknocks' Wii R.O.B. join the battle as well.
Kirby: I imagine that any real 'costume' for Kirby causes conflicts involving the hats. If that's not the case,
Swimming Goggles Kirby perhaps? Otherwise, I'd just invest in some of the alternate color schemes, especially those included in the Amazing Mirror and Squeak Squad, or the Brown Kirby seen in Air Ride. 'Shadow' Kirby, the black Kirby, should definitely be a priority color.
Metaknight: There's a very nice 'Samurai'
Quickdraw Metaknight model, again by Tocksknocks, and I'd like to see it in Project M.
Maskless Metaknight would also be a nice pick.
King Dedede: Personally, I'd like to see
Masked Dedede with a revamped hammer.
Pikmin & Olimar: I don't have much to say about Olimar. It would be nice if the
other playable characters from Pikmin 3 and
Louie could replace him, and the character slot was just referred to as 'Pikmin', but I doubt the PMBR would go with that.
Fox McCloud: An outfit based on
his father could be neat, or perhaps his
Assault appearance.
Falco Lombardi: I really do dig his
Assault appearance. Though, I guess him and Fox also have their appearances from
a certain Star Fox Command ending to consider...
Wolf O'Donnell: I think his alternate outfit is fantastic and he doesn't need another. Alternate colors perhaps?
Captain Falcon: Outside of a helmetless outfit, which I'm not sure I want, I can't think of any.
Pikachu: Where are my
party hats at? Honestly surprised we don't have them already.
Charizard: A
Clone Charizard skin based on The First Movie would be nice. I guess the PMBR has already decided against Mega Evolution outfits, which is a shame--I think both of them (Mega Charizard X moreso) would look just fine in the game.
Ivysaur: There's a
Clone Venusaur and a
Clone Bulbasaur in the anime, but not a Clone Ivysaur. I'm sure a skin wouldn't be a stretch though, right?
Squirtle: There's a
Clone Squirtle, but it's nothing special. Thankfully, I won't make the obligatory Squirtle Squad comment. But,
speaking of the Squirtle Squad...
Lucario: Really hating the PMBR for turning down the
Mega Evolutions right now.
Jigglypuff: Outside of the obvious
bow, headband and crown from Melee, there isn't much to say.
Marth: Two outfits come to mind--his
Awakening artwork, and his
SSB4 artwork.
Ike:
Vanguard Ike comes to mind as my favorite appearance of his.
Roy: His
Awakening artwork is just too good, and I know I won't be the first or last person to say they want it. I also wouldn't mind seeing Roy wearing
his father's clothes.
Ness: I really don't have any suggestions for Ness.
Lucas: The Masked Man outfit is great, but I don't have anything else to suggest.
Mr. Game & Watch: ...If anyone can actually suggest a serious alternate costume, I would be impressed.
Solid Snake:
Old Snake and
Tuxedo Snake come to mind immidiately. His
MGS2 disguise could also work.
Sonic the Hedgehog: This one's a little difficult--not because Sonic doesn't ever wear any other outfits, but because he doesn't usually wear much in general. He has a couple of minor outfit changes, like his
Air Ride appearance, but visibility issues do exist. There's
Werehog Sonic, which probably looks better in practice than you might imagine,
Darkspine Sonic,
Excalibur Sonic (without the sword, of course), and his
SA2 Racing Suit that come to mind, though.
That's pretty much it. As I mentioned for a few characters (Looking at you, ZSS), some changes to the team colors would be really nice. I've got partial color blindness myself, so I sometimes have difficulty with certain color schemes like Green Melee Falco. Of course, there's always Project Mars/Maritime/Mint for personal P:M builds, but I think it would be a great touch for Project M overall to have some of these adjustments.
I thiiiiiiiink that's enough suggestions for now.