Hey, I'm no visual artist--I can barely draw a stick figure--but I've done seven color maps now and they're starting to look almost right. Here are my quick and easy guidelines for making a halfway-decent color map:
1) avoid gradations. They look great in RGB, but once you convert to indexed color they turn into thick ugly bands of posterized color. You can avoid this with:
2) Your new best friend, the Grain filter. This puts what looks like tv static all over your map. Trust me, you want that. It gives a nice pebbled appearance in the finished project--I've noticed that Creation uses this a lot (or something similar). You can get some of the same effect just by adding monochromatic noise, but Grain seems to make the colors pop a lot more. This filter will let your colors fade from one to another--I used it on a map where I had greend and yellow grass, and it looks very natural. Just keep the contrast and intensity levels kind of low (or the colors get very trippy, very fast).
3) There's always textures. Bungie and Vista have both published texture libraries that you're free to use. These are patterns you can fill whole areas with (open the texture in a new window, choose "define pattern", then go back to your map, select the area to patternize and do a fill with "pattern" instead of "foreground color"). You might want to fade them a little (under the filters menu you can adjust the opacity) because a lot of them seem very dark to me, but they give you that Bungie look every time. I tend not to use them very much because my maps aren't supposed to look entirely like natural terrain, but when I do use them I always love the way they come out.
4) Don't be afraid to ask for help. Go over to Vista's site and ask on the editing forum how people make rocks, water, etc. There are a couple good step-by-step tutorials there for doing some basic textures, as well.
Hope that helps.
