What I did, was found a large map that had a quarter of it as all land, and selected this quarter, then pasted it into a new file (in Gimp) and saved it. I can then resize this file to the size map I want, and add all the necessary features (again in Gimp), lining up the water boundaries with those of the apron (as described by Pecunia in one of the early tutorial articles).
This technique was used on the Aisle of Plenty map, and also the Iceni Queen map (which is still under development, although the map itself has long been completed). The latter was wholly made in a single session of about three hours, from an old map of Londinium. You can make a completely original map in quite a reasonable time once you get the hang of it.
Sometimes I use the map editor to do colour shading, with reasonable success, but mostly I use Gimp. If using the editor to paint terrain, you MUST save often. I believe TM used a third party program to do the terrain on the maps that came with the game, but the blends were done in the editor. I don't find it necessary to mess with the blends at all. You can use pretty much any blend and it looks OK.
An alternative to the above technique is to start with the dds (and apron) from one of the existing scenarios, and use copy and paste (again in Gimp or a similar program) to customise it. You copy whole chunks of the map and judiciously paste them somewhere else, over map features you want to get rid of. This leaves join lines which you can disguise using the blur tool or by adding things like trees, etc. The idea is that your map cannot be readily discerned as originating from some other map. This was the technique I used in The Pink Lake (which came from the default map), Silk Purse, and The Final Deception. The last mentioned started its life as Caesarea, and when Aramann first tested it, it still had Caesarea's requests and invasions, little by little it became its own entity.
My first C4 contest (Bling, a mere 12 months ago) was made using the Djedu map, with no changes whatsoever to the map itself, but changes to the available commodities and trade prices and with mission requirements added, but no scripting whatsoever, it did not even have a cs file. This is a very good way to go first off, this way you don't have to master everything all at once, and you can make something very enjoyable and playable, and completely different from the original, without altering the map terrain at all.
[This message has been edited by goonsquad (edited 03-19-2008 @ 06:46 AM).]