First of all, good luck with the projects!
I would consider starting work with the program you are most comfortable with. You'll probably make the fastest strides.
I generally find that mapping(art really) comes to a head over a desired affect and that makes you change\choose programs. If your choice isn't clear it is probably because you haven't begun your map yet.
Failing that, just looking at your list, I'd suggest you start with Fractal Terrains and then use photoshop\gimp to get more precise. That's generally my process. Even compared to everything else I find FT is the best for starting a broad\large map project for gaming. You can slice and dice and everything fits together. You've seen it.
All that being said there are now a number of tutorials kicking around on this site. You could also start there.