Brinstar is legit, since the gimmicks aren't that hard to get around if you just play smart and try to maintain stage control.
Rainbow Cruise on the other hand... that's a different animal altogether. At least with brinstar you can just control your space and punish air campers trying to refresh their jumps... but on RC you can't do that. If the other guy is noticeably more mobile than you, you're ****ed. That's why MK dominates there, he's ridiculously quick and can cross from one end of the screen to the other without touching ground.
But lets set MK aside and consider a different end of the spectrum. Ganondorf, for example. Even if you were the greatest Ganon player ever, what chance do you stand on RC? You can barely move anywhere on that stage, other than the ship, without being in constant danger of getting gimpped or otherwise punished just for moving, and the stage literally forces you to do it! Anyone with low aerial mobility or a weak air game just has to play keep away until they get to the more ground friendly portions of the stage, desperately trying to avoid getting punished during almost half of the stage (realistically, more like 2/5). It's either that, or both you and your opponent are just trying to keep up with the stage as it rises, which discourages you from fighting each other. Why would you want a stage that discourages characters from fighting... in a FIGHTING game?!
The fact that the stage moves and changes isn't the problem. It's that it NEVER STOPS moving and changing. At least with Delphino, PS/2, or Frigate it changes, you fight for awhile, then changes again... The safest parts of RC are the top-left quadrant, and the ship. And honestly, does anyone really feel "safe" or "at home" on the ship? It just feels awkward to me. Wasn't it noticeably bigger in Melee? In Brawl I feel like the ship is like you're fighting on half of a real stage. Then the ship sinks, and they throw more areas at you that all feel like they're half-finished.
I have to give RC a big thumbs down. It's unfortunate, because I can appreciate the diversity it brings to the stagelist... It's just not a legit stage. Too bad they didn't port PokeFloats from Melee. That stage was actually pretty legit, and extremely underrated.