I enjoyed Dwarf Fortress random map generation because it simulated erosion pretty well. Small creeks started in the mountains and flowed to the ocean getting larger as it went. Deep valleys and waterfalls too in places made for interesting maps.

Be interesting if we can start getting 3D games with random maps that are realistically generated and have interesting features in the future.