Everybody, thank you for replying and your hospitality!
Now then, I didn't initially post every character's alternative costumes because the list was a bit too long, but I think I'll do it anyway just to double check myself against everybody else here. I will also include the origin of the "standard" costumes in this video as well. Some of the "standard" costumes are kind of ambiguous. (I have to admit that I got a few of these from following links from the links people posted here, so thank you for that. I also haven't researched everything 100%, so a few of these may be just kind of "meh.") Anyway, here it goes, everything right off the top of my head, plus what's been posted...
Dr. Mario - normal - Dr. Mario
Mario - normal - Mario Bros. Arcade (though his overalls became more jean-colored in Super Mario World)
yellow - Wario
brown - Wrecking Crew
reversed colors - DK Arcade
green - a weak attempt at dressing like Luigi? (This one I'm not sure about including.)
Luigi - normal - Mario Bros. Arcade
white - Super Mario Bros. (NOT Fire Luigi. Fire Luigi has the same sprite as Fire Mario.)
pink - Wrecking Crew (Even though Luigi was kind of purple in that game... but the fact that Luigi is in pink of all colors makes be believe that this is referencing Wrecking Crew.)
Peach - normal - Super Mario World, but became more detailed in Super Mario 64
brown - Daisy
white - Dr. Mario - nurse Toadstool
Bowser - normal - Super Mario World, but became more detailed in Super Mario 64
Blue - All Night Nippon Super Mario Bros. art
Yoshi - normal - Super Mario World
red, blue, yellow - Super Mario World
pink - Super Mario World 2: Yoshi's Island
Donkey Kong - normal - Donkey Kong Country
Captain Falcon - normal - F-Zero artwork (or F-Zero X?)
black - Japanese F-Zero X commercial cosplayer
dark red - F-Zero X - Blood Falcon
white - F-Zero X - Jody Summer costume
green - F-Zero X - Pico costume (maybe? What do you think?)
Falco - normal - Star Fox 64
Fox - normal - Star Fox 64
Ness - normal - Mother 2
blue - Mother 2 - Ness's reflection in Giygas (I think this is pushing it, but I'll include it in the video anyway for the hell of it.)
(I'm surprised that "pajamas" Ness with bedhead wasn't included as a costume, but whatever.)
Ice Climber - normal - Ice Climber
The last two costumes let Nana lead. (Must make feminists happy....)
Kirby - normal - Kirby's Adventure
yellow - Kirby's Dream Course - Keeby, or Kirby Super Star - Beam Ability (I'll have to see which came first.)
blue - Kirby Super Star - Ice Ability
red - Kirby Super Star - Fire Ability
white - Kirby's Dream Land art (Though, if I remember correctly, the Ice Ability in Kirby's Adventure also turned him white, though I think it had a blue tint to it...)
green - Maybe a reference to how he looked on the original Game Boy, with its green display and all.
Samus - normal - Super Metroid - Varia Suit (Yes, I think it looks more like her in Melee than her starting Power Suit in Metroid.)
pink - Metroid - Varia Suit WITH MISSILES SELECTED (When Missiles are selected in Metroid, Samus's visor turns blue, regardless of the Suit she has. Her visor is blue in Melee with this costume.)
purple - Super Metroid - Gravity Suit
Zelda - normal - Legend of Zelda: Ocarina of Time
red - Legend of Zelda
light blue - Legend of Zelda: A Link to the Past
Link - normal - Legend of Zelda: Ocarina of Time
red - Legend of Zelda - Red Ring (I'm just going to show this since the red costumes in the following Zelda games were taken from this.)
blue - Legend of Zelda: Ocarina of Time - Zora Tunic
light blue - Legend of Zelda - Blue Ring
dark grey - Zelda II: Adventure of Link - Dark Link (What do you think? Or is it too weak?)
Young Link - normal - Legend of Zelda: Ocarina of Time
All of "adult" Link's alternative costumes also apply to him, but I'm not going to show the same thing twice.
Ganondorf - normal - Legend of Zelda: Ocarina of Time
Pikachu - normal - I imagine Pikachu existed in color in art sometime before Pokémon Stadium (Japan) came out. This is definitely one I'm going to have to do some research on. Or any knowing persons could just tell me. ;D
red hat - Shiny Pikachu & Satoshi's hat from the anime (--___--)
Pichu - normal - probably in artwork, or in Pokémon Stadium 3. (2 for everywhere else outside of Japan.)
Jigglypuff - normal - same thing as Pikachu
Mewtwo - normal - Probably Pokémon Stadium, I can't see a lot of artwork for Mewtwo before the first anime movie made him popular and "evil."
green - Shiny Mewtwo
Mr. Game & Watch - normal - design is generic, but seems closest to the falling Game & Watchs in Fire and Parachute.
red, green, blue - referencing the colored LCDs in the Tabletop and Panorama series
(I'm a physics major in college and I wasn't aware there were colored LCDs in the 1980's... as color LCD monitors and such are recent technology. I had always thought that the Game & Watch handhelds used
Super Twisted Nematic Display to display the individual electrodes (or "frames") of movement. As that page says, I knew that color LCDs were developed in the 90's, but the Tabletop and Panorama series were made in the 1980's... Weird.)
Anyway, enough of that... >_>
Marth - normal - Fire Emblem 3
white - Fire Emblem Thracia 776 - Leaf
Roy - normal - Fire Emblem Fuuin no Tsurugi
(?) - GBA Link Room Battles (I've never done this because I don't have multiple Fire Emblem cartridges, so looking at this or acquiring the footage for this is going to be a problem.)
gold - Fire Emblem 4 - Neutral Fraction
Anyway, that's enough for now. Thanks for all of your help!