One of my favorite engines for creating random maps uses Voronoi diagram methods as a starting point, then expands on them. The engine first creates a Voronoi diagram, then runs a smoothing filter of sorts to redistribute the points a little more evenly. The engine then applies various noise functions and calculates a graph (node-based diagram, sort of) to determine placement of biomes and linear features such as rivers and roads.
I can’t really do justice in a brief description, so I’ll include a picture from the page that does the best job describing what’s happening.
The image above is taken from http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/, which explains in much greater detail than I can explain here how it is produced. The linked page also includes links to online generators using the methods described on this linked page.
I’ve always felt this page deserves more attention — from me, if from no one else. There are some fascinating ideas regarding random terrain and map generation that I’d love to find time to explore.