Don't have 80,000 provinces, have less provinces and less places where battles can occur and then create more options within them.
Personally I am a big "more provinces is better" proponent. But I like things like city-states, small nations, etc.
But I agree on more options. As it is now, you can only hit your army on their army. You can't, for example, fight a Guerilla War. My iberian ancestors, the Lusitans, gave the romans immense casualties by fighting guerilla war for years, even through the Roman Empire was huge and they were just a small tribe. Romans literally had to win by making Viriato's bodyguards murder him - which spawned the saying "Rome does not pay traitors."
I was recently reading The Alexiad and it was so interesting to see many of the tactics which pre-modern armies used. So much deception, for example.