Underpaid... You can Recolor or Alter Terrain Graphics as you like. Just apply the same procedures to all terrain so they will all continue to blend as they should. Example...if you adjust the Contrast for Grassland, you will need to apply this same contrast adjustment to all terrain. The biggest task is to maintain the same Terrain Look with all terrain files so the colors and contrast are blend together well. For example, Water is in with the other land terrain files so if you change the color of the water, you must change this in all of the files with water in the various land terrain. Be sure to maintain the indexes for the Magenta and Green shades on the Terrain palettes.
PSP is is best for editing graphics because it will allow you to be able to do more easier and better. As for exact procedures to change Graphics, specific questions are necessary concerning any single procedure because there are too many possibilities to cover with any general answers.