I have a feeling understanding the terrain generation is similar to understanding the diamond square algorithm. I've thought on and off about generating random terrain in a game and through my googling found
this page. If you look at some of the examples of inputs you can have to alter the algorithm you will see the are pretty close to the sliders you have in warband to generate the terrain laydown.
Some other games that have interesting world gen are dwarf fortress, for a sort of over the top one, in which he generates temperate zones, mountains, rivers, has an erosion process, then simulates the world history to place villages, farms, etc etc. It's quite amazing actually, but anyway i'm rambling.
So in warband, maybe a quick fix for this is to use 'fake' cliffs in generation. You just use flatter terrain, then instead of dropping a castle, you have an object that looks like a real cliff face and place that between terrain. Since it's an object you probably won't need to mess with the ai mesh too much for the ai to avoid it. The problem here is of coarse set pieces in random generation can feel very repetitive over time, ie daggerfall/oblivion. But that might be a way to perk up some hand crafted maps.
The other solution might be to change the way impassible boundaries are placed. If you could for example take any slope beyond a certain steepness and make sure there is no ai walk mesh on it, and also add boundries for the player to not be able to cross, that could provide some more interesting maps, but you would have to be careful else you would end up with a situation where neither army can actually reach the other one.
I read an interesting paper someone had done talking about using cellulara automata (like the oldschool 'game' life) to generate random caves in 2d. It was a pretty simple algorithm in the end with some parameters you could use to change up your structure, but always guaranteed you had a path for the player to walk and it was all connected. So you could get some pretty cool box canyon maps by using this algoritm to generate a 'floor' in 2d, then just rise the z axis of all the impassible spots to look like canyon walls, or even do it randomly so some are higher then other and a few more are just little bumps. Either way you'd get a pretty cool looking cliff terrain.
But honestly if you think about mountainous terrain, an army wouldn't generally travel through random areas. You would most likely stick to a pass or well known route that had enough room for your troops to maneuver. Otherwise if you were traversing forest or mountains you'd probably have a small force that was capable of fighting there or trying to sneak around a flank or just necessity demanded you go through it. But yeah I doubt very much that a force of 100+ guys would be walking randomly in mountains so you end up with a fight on a steep cliff or really with no place to maneuver.
So maybe there should be some set pieces that line up with the overland map, like there is a well known mountain trail between towns, every time you get in a fight in the vicinity of it you get mostly the same map.
With any game there is always lots of room to improve and change things, just a question of time and drive