Would love to see the Robot Masters rematch room from any of the Wily fortresses, that way, the terrain would change constantly (but not drastically).
I'll use my example with MM2 robot masters.
The stage begins and you all fight in a large room with several (8) telepods. At one particular moment, they will all start flashing. If a player lands on one of them while they flash, the room will change.
METAL MAN: Flat stage, but the floor moves to the right. Occasionally it will change to the opposite side.
FLASH MAN: The stage has some stair-like patterns of big chunks of ice.
BUBBLE MAN: Spiked ceiling, and low gravity. May have bubbles which damage you.
AIR MAN: It's cloudy, and wind will occasionally push you to the sides. No ceiling (Star KO possible)
HEAT MAN: It's just flat, and flames might rise from the floor at any given time.
QUICK MAN: Ground has ups and downs. No ceiling. (Star KO possible)
WOOD MAN: Leaves may fall from the ceiling to cause damage.
CRASH MAN: Flat, completely neutral. No ceiling (Star KO possible)
(To go back to the main room, a player would have to enter the telepod in the new room once it starts flashing again)
It's all very simple tweaks to the terrain, so that they can work on some of these. I wouldn't want them to be TOO random, so simple ground pattern changes, and a few effects here and there ought to do the trick.
Also... one would only be able to KO by the left side of the screen, unless the current stage area had no ceiling.