The One made Sauron so bad-ass. Plus he was quite a large humanoid.
On the "Winner Take All" point of how many turns does the attacker have to "cap" the battle? Sounds like a perfect opportunity to incorporate some sense of logistics into the game. Make N proportional to the number of baggage carts that the army brought along with it, and make those a viable target for the defender to capture to cause N to suddenly drop and put the battle into a "sudden death" mode.
Of course spells, etc... can reduce the need for baggage carts.
Morale should figure into how long battles last also. Morale systems should have some play in both the strategic and tactical sense. E.g. Bring along some units just for the morale bonuses. Assasinate such units of the opposing side. Tactically, there should be local morale at least in super simple form. E.g. Have a sense of center, and ight and left flanks. E.g.Your flanks might crush the enemy flanks, but the opposing superhero with some magic combo might send your center fleeing for their life due to poor morale, effectively ending the battle.
Morale has real significance in battles since the beginning of time, and without it the units are just Jaga Fett clones.
On the "combined arms" aspect, consider that one's mount makes the benefit of being mounted. E.g. some mounts provide speed (flanking) or even allow the 'Parthian shot'. Other mounts provide shock (i.e. an initial bonus in the charging due to mass) (e.g. mammoths) or are essentially "hitpoints". Some mounts give a combo of the above.
Shock units that successfully hit should lower some of the enemy morale.
On "randomization", generally any randomization makes the game like craps or slots whichs basically negates strategy. So except when gamboling on a random benefit to try to tip the balance of a stalemate, I think randomization should be limited. Slight variance is to be expected, so light randomization is to be expected. In other words if two melee units of equal base strength face off, you expect a variable outcome, but if the omega super tank faces against the wimpy melee unit you do not expect variance to favor the wimpy unit without divine intervention.
That said there may be room for some units that throw some randomization on the battlefield. E.g. stealth units that just might assasinate a general or hero, etc...
Thresholds is good. No need to waste the gamer's time with pointless skirmishes that the AI provoked, or were the result of an "attack move".
Terrain considerations, that's great. Great place for engineer-units as well as special abilities to negate/ablate those (e.g. fly over the fort walls, burn down the forest that the archers are hiding in). I'd rip the hill/guerilla promotions from CIV4 for starts, as well as give some field fortifications that can be improvised during a battle. One thought: for each engineer in the army, allow the defending player to set up some free field improvisations (e.g. palisades, traps, mini balistas,etc..).