Besides The GIMP, you may want to look at Inkscape. It's more akin to Autorealm in being a vector graphics editor (The GIMP works with raster graphics), though it's a much more general one. You may find better suited to your your way of working, or you may not, but I recommend you try both. You may even find it best to start in Inkscape and finish in The GIMP.

If you want to try playing with a real Geographic Information System, which really isn't what you asked for, but which you may want if the cartography bug bites hard enough, there's QuantumGIS. It will let you do things like switch projections or check the distribution of orc tribes against the carrying capacity of the local ecosystem to make sure they don't starve themselves out.