What would be wrong with a system where all the damage in a fight would be known in advance? E.g. in a 25%/75% fight the loser would die and the winner would suffer 1/3 as much damage.
No randomness. No cheating called for. Totally fair. Everybody's happy. Nobody's astonished.
Battle tactics would be virtually the same, you'd still attack when you knew you'd lose individual fights, then clean up the damaged defender with a fresh unit. It would help to know more accurately how many units to bring but that's all.
Yeah yeah go ahead, tell me "real life is full of uncertainty". I play computer games because I can't deal with real life
Give me determinism.
If you want to play Diplomacy, go play Diplomacy. Determinism is fine for seriously abstracted games, but Civ isn't quite on that level.
To some degree, I would agree that the effect of the RNG on combat should be reduced, but only in the face of adding leadership for units, command chains, logistics, effective combined arms (like merging every all the individual units you build into divisions, corps, and armies) to account for effects the RNG is currently accounting for.
It sounds good until you realise that stacking will make it impossible to clear off damaged units, as they will always be defended by stronger units. It also means that AGG leaders will be completely overpowered, as even a 10% boost in strength will guarantee that they die and your unit lives (albeit damaged). That way, instead of needing somewhat more units to clear out a stack of AGG units, you'll need double the number of units to get rid of them (because every single first-hitter is going to lose). Civ5's deterministic combat is a step in the right direction, but then it takes 2 steps back and trips over because it doesn't fit into an empire-building game and there is no room to maneuver.
I've also been of the opinion that unit healing should not be free, there has to be some kind of hammer-associated cost to it.
Combine all the units into a single stack, which you give general orders to (and possibly assign generals to). Complete and utter routs would be relatively rare and would require a lot of planning and the right leadership to execute--usually, the defeated force would be pushed back and be "passive" until it regained cohesion and could fight again. Having dedicated pursuit forces separate from your main army could keep pace and inflict more casualties on your opponent.
The unit healing problem is the worst part of the Civ series. You could always have a basic AGEod-style replacement system where you have to produce special replacement units that will refill your units on the field. Or have a Paradox-style manpower system.
Example: I have a force comprised of 8 musketmen, 2 grenadiers, 1 cannon, and 1 cavalry, each with 100 points of strength. It is merged into one super-unit, and proceeds to engage an enemy army of similar composition. After a battle, I have lost 230 points of musketmen strength, 30 points of grenadier strength, and 70 points of cavalry strength. No unit is eliminated, but they are all weakened.
I have built two gunpowder unit replacements, so after letting this force sit in a city or a fort for one turn, 200 points of strength are returned to my muskets and grenadiers. However, my cavalry is still weak because I didn't have a cavalry replacement ready to go. In another battle, if I lose the remaining 30 points of cavalry strength, that unit is removed from the game and I have to rebuild the unit from scratch.