Anybody with actual intelligence will most likely figure out how to basically work any starcraft map. If they can't, then that's what experienced players are there for, to teach them. But if it's one of those people who leave because they can't figure stuff out, then it's probably best that they aren't ruining the game experience for the rest of the players.

Now, that's really only for maps that don't require most or all of the players to be participating. If you have a map that's complicated and requires all the players to stay and understand how to play, I've often found that the best way is to include detailed instructions in the briefing, as well as a trigger-activated help menu in-game that is basically a shorter version of the briefing. You will occasionally get the idiots who won't bother reading either, and don't bother staying to learn to play as well, but there's really not much you can do about that besides making the map simpler.

Making the map simpler may not help, there is a limit to what you can teach in a single game. Even for a relatively simple game like spawn d, the best players can write several pages of strategy.

That does not mean noobs cannot enjoy it, it depends on who is playing.

Just another idea (I havent read anything apart from first post): Ease players into it the same way all RTS ease players into using units: by giving them the ability one by one (and/or make a scenario where you need them)

Have in game messages

I doubt you even read anything...it was stated that ingame messages ddnt work.