Grain that is used in my maps is primarily used to add some natural variation to the terrain.
Another primary thing that I do is using the Airbrush set to dissolve on a Photoshop Layermask to mask out unwanted parts of the layer. After happy with the masking I then either smudge or Blur the layer mask which tends to give the transitions between... say grass & sand a natural variable effect.
Another secret I've found is to set up a small palatte of colors to use in your map initially which come from the 256 color palatte & base your map primarily from them. When converting to Indexed color many of your colors will already be in the palatte & not have to be dithered... thus leaving more room for gradations that must be dithered.
Designers use this same process when designing web pages... a non-dithered color will compress further & download faster than a dithered color. Same principal here, thought he download time does not apply. Just the part about dithering.
If you have further questions, please feel free to stop bye Creations Hotline server. I saw Sephiroth there this weekend breifly, but he never asked any questions.