A lot of the software links in this thread are dead (all geocities links for example).
One obscure tool for creating random maps is the Dominions 2 map creating program DomMap 2.17. Currently you can get that from here, but there is no telling when that site ceases to exist, since Dominions 2 is a very old game. I may host the files myself later just to preserve them. The program itself is free and can be used as a base for creating landmass shapes, but it will require extensive editing to get anywhere.
Instructions on how to use this utility: Read the documentation that comes with it. I recommend using the following color code switches to produce a visually pleasing map where you can immediately see what's what:
Plains: dcbe9b (220, 190, 155)
Sea: 87afcc (135, 175, 204)
Tundra: dcebf0 (220, 235, 240)
Swamp: 969673 (150, 150, 115)
Forest: 3c733c (60, 115, 60)
Farm: d2dc73 (210, 220, 115) OR bed282 (190, 210, 130), whichever you like, but I think d2dc73 is slightly better.
Mountain: 7d5019 (125, 80, 25)
Waste: e6b473 (230, 180, 115, bit more faded) or e6b464 (230, 180, 100, brighter) both are relatively good
Landborder: cd3200 (205, 50, 0)
Seaborder: 414187 (65, 65, 135)
If you want maps with few borders, just set the number of provinces to a very low number (one sea, one land). If you want maps with ready-made borders for kingdoms, principalities, states and whatnot, pick the number you want and the program will do that for you.
The program produces the maps in .tga bitmap format, and also produces a .map file (specific to the game Dominions 2: The Ascension Wars). The map file is readable in any text editor, and contains the random seed number for the map. Running the program with the same seed value will always produce the same map, so you can write the number down for maps you like and fiddle with the color settings if you want to try something else.