1)

is not caused by the RNG. It is caused because the number of hitpoints has been reduced, thus reducing the number of random trials. Bring back FP and 10-40 HP, preferablly 100.
2) No armies, free-battlegroups.
3) Fighting. All fighting would be between battlegroups, since you are not going to face 2 archers, 4 spearmen, and a Horsemen with a single Warrior. When groups are meeting, you can choose to fight or retreat(you figure out you'll lose).
3A) You'll then get a few options on how to deploy forces on each side. Some options would include "Ranged Skirmish", "Spear Wall", "Cavalry Skirmish", "Infantry Charge", "Cavalry Charge". Defender gets best terrain for that formation.
3B) Battle wold be calculated automatically, but you coudl see it happen(in Ultra-Hyper Speed). Also, what happens would be based on what his happening and troop positions.
3C) You can pause combat to order one of these battle commands: Full Rush, Pressure Attack, Tactical Withdrawl, Tactical Retreat, Full Rout. Basically once you make an the first battle commmand, the only options left are Full Rush or Full Rout. After that it is up to the troops to do what they were ordered.
4) New Unit Values - There are a few new values units will have, basically they exist to explian combat.
4A) Endurance - Tired units fight at much lower efficiency then fresh units. Endurance is a measure of how easily units lose vigor in battle.
Notes: The RPS system will be simulated through how combat works. Sicne archers suck at melee and horses are fast, cavalary beats ranged. Since spears are slow archers tear them up. Since spears have high defence, cavalry tire and soon do worse in combat.