Map making utilities generally fall into 2 categories:
1. Programs that convert bitmap graphics into a map. (Dragon, Map Generator 2, UO Landscaper).
2. Programs that let you edit the map 1 block at a time (World Maker, WorldForge, etc.)
If you are going to build your new map from scratch, I would recommend that you start with a bitmap-to-MUL program for the large work (laying out your map terrain, etc.); and then use a map editing program for detail work and touch-up.
Recommended programs:
For your bitmap-to-MUL program: Either Map Generator 2 (recommended) or Dragon.
Dragon uses 1 bitmap for both altitude and terrain, so it might be a little easier to use - however, it doesn't support 3-way transitions so your map will need a lot of touch up, especially the coastlines.
Dragon is also restricted to 256 terrains/altitudes (because it is all on 1 indexed bitmap with 256 color palette). Map Generator 2 and UO Landscaper both use 2 bitmaps, 1 for terrain and 1 for altitude, so basically you can have 256 different terrain types, and 256 total altitude conversions - a lot more flexible. Both programs also support 3-way transitions, so less touch-up needed with completed maps. However the learning curve may be a little steeper.
UO Landscaper is similar to Map Generator 2 in the way it works, but it has some bad issues with memory management which makes it difficult/impossible to compile a Britannia sized map. So I would not recommend UOL for a Map0 as you might not be able to compile it.
For your direct map editing program: World Maker.
Punt is the author of both Map Generator 2 and World Maker and visits here from time to time.
I believe you can find all files at either:
http://punt.demuria.com
or
http://www.ryandor.com/files
_________________
-= HellRazor =-
Shattered Sosaria is coming!
http://www.shatteredsosaria.com