Torstan's game maps are as good as any I've ever seen. I'd trust his advice.
The Gimp and Paint.net or Inkscape are all really good choices because, well, they're free. You may find they give you everything you need.
What you choose will depend on what you expect or need. Speaking broadly....
If you can draw elements (houses, hills, buildings, durngeons etc...) free hand then you will probably want a drawing program. Vector drawing or raster drawing:
Vector - Paint.net, Inkscape, Corel Draw$, Adobe Illustrator$$
Raster - The Gimp, Corel Painter$, Adobe Photoshop$$
(And many others.
Another approach is sort of the stamp collecting approach. You gather your elements from other artists or third parties. You can of course make your own elements too but the elegant part here is you dont have to.
Campaign Cartographer uses this approach in a Cad program which is elegant because the vector shapes scale very easily and rotate\render cleanly.
Dundjinni also uses this approach but the elements are raster not vector - overlay a picture of a building on a picture of a field.
Their are many other products and the above products have more value than I have listed. If you have an eye for maps you can accomplish beautiful work with almost any graphics package.
Thats why I'd start with the free packages and give www. cartographersguild.com a look. Lots of friendly people. There's even some work by Torstan!
Sigurd