I've beaten an MK main on both Brinstar and Frigate in one set...I don't think they are too terrible.
I guess if the MK main know how to destroy on Brinstar, don't take him there, but if you think you can deal with the player there for some reason, I think you should do it, G&W is great there.
I only fear two stages against any character, and that is FD and YI, so I just avoid those two, I don't think anyone is too much of a problem on other stages. If you're going to lose to someone on any other stage other than those two I mentioned it's probably going to be because they are a better player than you.
^Just my thoughts.