I think it'd be cool if every series got a boss. There's already a Mario, Pokemon, Earthbound and Metroid boss. That leaves a bunch of other series. Let's go down the list.
Donkey Kong-KAOS from DKC3 would probably be the easiest to implement, but any of the bosses from DK64 would be cool too
Yoshi-Probably Kamek.
Wario-I could pass on this one, but I think the Mike robot gone corrupt would be somewhat interesting.
Zelda-A lot of options here. Beast Ganon would be cool, when Link and Zelda revive Ganondorf before the Great Maze. Any bosses from Ocarina of Time, Wind Waker or Majora's Mask could all work.
Kid Icarus-I've never played this game. Isn't the final boss the Devil?
Ice Climbers-No idea. Maybe a polar bear.
R.O.B./Mr. Game & Watch-Nah.
Kirby-Seeing as Marx and O2 both have themes in the game already, they could work.
Pikmin-Titan Dweevil, Emperor/Empress Bulbax, Burrowing Snagret, so many options.
Star Fox-Andross seems most obvious. An aparoid (from Star Fox: Assault) could also fit in well.
F-Zero-Black Shadow, anyone? Deathborn would be cool too.
Fire Emblem-Ashnard, Ashera, or a dragon. All would be very cool.
Metal Gear-RAY, REX or GEKKO. Liquid Snake is plausible too.
Sonic-Dr. Eggman and one of his crazy machines. But Chaos would be much, much cooler.
Of course, with all these bosses, the SSE would need to be seriously longer. Given enough time I think I could work it out.