I would imagine generating interesting terrain could be as simple as a perlin noise algorithm, then assigning elevations or terrain types to the different values. Where I'd imagine it getting a little tricky would be intelligent balanced placement of buildings, roads, bridges etc.
Random map generator, Hidden Map and a setting for Neutrals: Weak, Normal, Strong and Random. Warbarons would be ten times better if these were added. Random maps are the best way to play these kind of games. Pre made maps suck.