I agree that a fractal map would look more aesthetically pleasing, and things like the "join" between terrain triangles being blended out would make the maps more realistic. However, I have no idea how to go about making these maps.
However, many years ago I used to play Simu Trans (http://www.simutrans.com/en) a lot ... a great deal in fact. For me (as a non-coder) the best implementation that Hajo ever made was to allow the import of grey scale images that created the maps. The level of grey, from black to white, determined the height/elevation of the terrain. This gave a base map that could then be populated with trees and stuff.
I particularly liked this approach because it meant I could make maps I liked from scanned images (playing the Faero Islands was a strange habit I had back then)
I know that Simu Trans has moved on a lot over the years, and I don't really play it any more, but you should be able to get plenty of ideas for this concept from his code.