There's one very important thing that comes to my mind out of random maps:
They are rarely, well, personal. Take Civ for example. Most of the areas are just small plots of random terrain with little feeling to them. There is rarely a large desert or mountain range or something like that. There's a mod to Civ4 called Fall from Heaven, which has a very good random map generator, since the map is a local one, instead of the whole world. This allows things like valleys and jungles and such to be created, and it adds a lot to the immersion of the game.
So, areas that are consistent terrain-wise are cool, especially if there are special things in them AND the game generator names them as well. Let's say there's a huge swamp that has a volcano in the middle of it, the generator then places a name to the area "Smouldering marshes". How cool is that? Very cool, I tell you. 
There should be a lot of areas that are impassable, harmful or slow them down to most units, like mountains, huge forests(of doom), bogs, valleys, hills and such. It feels wrong that an area is mostly grassland with a few hills here and there, since they don't really create a "flow" to the area, and you can't place forts and such in narrow passes since the enemy can easily evade them with no harm. If they must go through a poisonous swamp or a harsh desert that kills much of their army, the idea of assaulting the fort seems a lot better.