First a bit of vocabulary:
Squad Size — it’s used in the world map encounters and it’s the amount of troops in one slot (out of the five slots you have available for each battle). The only way to increase this is though the “Squad Size Upgrade” technologies.
Training size — the amount of troops you train in one slot in your military training buildings (you mentioned barracks). That’s what increases, when you build/upgrade Armories.
World map province difficulty — the ratio of your squad size vs. enemy squad size.
The squad size of the enemy is fixed when you scout a province (it’s derived from the distance from your city and the cost of scout). Afterwards it doesn’t change. There are generally two ways to reduce the difficulty (ratio):
1) Research more Squad Size Upgrade technologies (as Bor de Wolf 1965 said). It increases your squad size, which affects the ratio of your vs. enemy’s troops and therefore makes the fight a bit easier.
2) Research “Advanced Scouts” (the first research of many chapters, but not all, especially not the highest ones). That lowers the cost of scouting new provinces, which makes the enemy squad size lower, which makes the fights easier. It does NOT help you with the already scouted provinces, because the size is already fixed there, but it applies a to all newly scouted provinces.