In regards to the "richness vs. random" discussion.
An option that I thought of is we could have some set maps, but then goodies could randomly be scattered around.
An old tower that a few units could fortify and defend from.
Random itesm like swords, armor, potions etc that the first unit to gets a related bonus for the duration of the fight.
Some battles could randomly be "capture the flag" - each side has a flag behind their lines, and the first side to grab the flag and return it to their own flags position (while defending their own flag) gets a big morale bonus for the duration of the battle. The unit carrying the enemy flag would have a flag icon above it, and if killed the flag reappears at it's starting location
Lots of other possibilities.