Realistic Wish for new stages:
Skyloft from Skyward Sword
It could work a lot like Delefino Plaza did in Brawl.
Comet Observatory from Super Mario Galexy:
Placed in front of the main spawn point, and the stage parts modified to have parts where you fall off at.
Return of Princess Peaches Castle:
But cluster the town around the castle, and have a day and nighttime edition. (Daytime Edition having some of Bowsers Minions causing shenanigans and Nighttime Edition being the festival from Mario Galaxy)
Skytown from Metroid Prime 3:
It’s setting is just so perfect for a Smash Bros Stage!
And on a related note, City in the Sky from Twilight Princess:
Rooftops of Coreria City: (Sorry for the bad image, I couldn’t find anything decent)
Like Forside from Melee, but with more Spaceships.
The Begnion Tower from Fire Emblem:
Inside the tower, as you are gradually raised up you see several battles going on. You eventually get attacked by Dragons, Wizards, and Ashrea at the very top.
The Starcutter from Kirby:
Sort of like Rainbow Cruise from Melee, but with Kirby.
Rainbow Road from Mario Kart:
I don’t care witch one, just as long as it’s Rainbow Road and not Mario Circuit.
Semi Realistic Wishes:
Kamiki Village from Okami:
The stage itself would be placed near the giant Sakura Tree, and the village layout would be modified to place the village behind the tree instead of the Ocean.
Also have a Day, Night (fesitival), and Evil version of the stage.
The Village from Resident Evil 4:
Stage is on top of the house that had the Shotgun in it. Zombies are swarming the ground so that is why you die when you fall off.
Inside the Tower of Salvation from Tales of Symphonia:
Related: Inside Derris Kharlan. I couldn’t find an image of the location I wanted, but it is essentially in the final part of the dungeon.
Talims stage from Soul Caliber 2:
Lots of overhanging stuff to jump on, so it is a perfect fit.
Or the Cathedral.
Unrealistic Wish for new stage: Scarlet Devil Mansion.