Small unwrapped maps are easy enough for people to generate for themselves. So any combination of...
A) large or more (the game defines large as 20 prov per player)
B) satellite photo
C) fantasy maps (not my cup of tea to use known maps from other sources but some like it)
D) hex or other "fair grids"
E) balanced for multiplay
F) wrapped
G) themed scenarios
H) Creative (multiple layers, etc)
As to programs....
Using map generators from other games seems like a good idea. Dig up any X4 games you have from the last decade and see if they have a map editor.
And you might look at this directory
http://www.dom3minions.com/RandomMaps/projects/GIMP/
Those were created using a random generation script in the free GIMP paint program. GIMP is powerful, but not the funnest to learn
And here is a link to a Dom2 generator that is still running. Feel free to use any of these as a base for a new map. There is a new batch of maps generated every day.
http://tinyurl.com/2ofqzy
I hope to finish something like that for Dom3 one day.