New stages? I'd probably go with like...
A pipe maze stage probably, about the only basic Mario concept we haven't seen fleshed out yet and would make a good "home stage" for Piranha Plant. Would probably be a pretty large and loop filled stage with zero competitive merit.
A traveling cave stage where the main platform is riding along minecart rails (callback to tons of DKC levels really). The stage's interactivity would be as elements scrolled on of course.
A Zelda-1 dungeon level! A lot of different room block shapes would correspond to different platform lay-outs that would shift as 2d Link in the background art transitioned between rooms. Could be a super cool level if done right.
Chozo Ruins (MP1) as a huge Temple-esque stage
Bowser's Castle as a PS1 style "transforming" stage with each transformation being based on one of the four doors. IMO the Yoshi's Island style Bowser's Castle would serve more design good than using a basic Mario one by giving Yoshi stages more variety and by taking honestly the most visually interesting Bowser area in the first place.
Honestly hard for me to care about the Kirby series...
We're pretty low on reasonable Star Fox level concepts that embody the series well honestly. Maybe you could have some stage like Bolse where you fight on top of the station and just can see the level being played out in the background (with the station being just about to be destroyed as time expires).
Pokemon is already pretty fantastically represented honestly, but if you needed another, you'd definitely want to go for a pretty natural environment that has nothing to do with legendary Pokemon since all of the current Pokemon stages are either urban areas or legendary/ruins style areas. Something as simple as a Viridian Forest stage with no shortage of Caterpie and Weedle hanging out in the background could work.
Too many easy choices, but I think Giygas would be probably the most bang for your buck. The stage would literally use the EarthBound graphics, and the actual ground would be the HP meters! They do, of course, move up for each character's turn and would become intangible if a character died (which you'd have plenty of time to react to thanks to the rolling HP meter).
You could pick almost literally any course and make it work, but since we already have basically every angle of fighting on tracks (touring along like PTAD, riding cars from behind on Mute City SNES, riding cars from the side like Big Blue), your next best angle is probably having an "eye in the sky" view of one of the F-Zero tracks, fighting on some generic tech-looking platforms that look like an announcer's booth, and have some super cheesy announcer commentating on the race happening in the background while you fight in a super over the top way. You probably think that seems lame, but you aren't considering the merits of hearing BLACK SHADOW HAS TAKEN THE LEAD! HE HAS BOOST POWER! being yelled with incredible enthusiasm in the middle of a smash match.
I haven't played a ton of FE games, but most of their environments are super bland which makes the current stage design direction of more generic stages that could be from any FE game make a lot of sense to me. What we never get a sense of is the scale of an actual battle so I'd go with a touring stage moving around a very much active FE battlefield as you stop in to see lots of actual fights occurring. You'd probably want to base it on either FE10 or Fates so you could have real characters on both sides if you didn't want to be fully generic again, just pick a mission that was a big moment where both sides really went at each other (the last mission of chapter 3 in FE10 would be a really good pick if you went with that game).
That's all of the 64 and Melee series that reasonably deserve another stage (sorry
and
but you really don't deserve any stages beyond the garbage you already have). Most series newer than that are 3rd party or otherwise also really don't deserve more stages. Maybe there should be another Pikmin stage, but I wouldn't know where to start on that since environmental diversity is not one of Pikmin's strong suits so a third Pikmin stage would probably look pretty much just like the two we have now but with different geography and some different Pikmin monster being a hazard so kinda boring really.