Haha yeah it's impossible to start the game in some areas without cheating. At the very least you'll need to remove the fog of war (truesight: ctrl + T with cheat mode enabled) to see if where you're going has a big mercenary or bandit party. I personally just went out and recruited some of the troops I wanted, by teleporting around the map and using the cheat for leveling troops up. When I had 60+ troops I stopped doing that, because by then I wasn't being ganged up on so much anymore.
The most difficult places I've seen so far are in the Rhodok, Sarranid and Kherjit areas. There are large mercenary bands (in decent armor and a fair amount of good archers; even when fighting 100 vs their 30 I still manage to sometimes get a few of my men killed by their archers) in the Rhodok and Sarranid areas. The Sarranid area, in addition to the mercenaries, has the desert bandits, which are mainly mounted troops. What makes them tough is that they're so fast on the world map, impossible to run away from if you're just starting out. Kherjits have the same problem, but with the Steppe Bandits. The other areas have relatively slower bandits and you can actually avoid them if you're careful.
I figured they'd fix this soon anyway. The beginning of the game just needs to have reduced spawns, including the strength of the parties. I noticed that, by comparison, patrols and other bandit-hunting parties are like 20-strong while the bandits can go up to 50 in a single party, and often attack in groups, so the poor 20-strong patrol will sometimes be facing like 120 bandits. D: