I'm finding that non-siege units are more important than I'd originally thought here.
My current game is on the tiny lake-heavy map, the one with the name I cant remember. Crazy map, that. An H/N/N game to be exact.
I'm on turn 21. I've had 6 bandit keeps pop up, and generally these were close to each other.... heck, 3 of them popped up in a perfect line.
But anyway, the very first thing I did was send as many human units at them as I could; I think I had 3 military buildings setup on both red and blue side within 5 turns, which then charged at the first and second bandit keeps.
It was important for one reason: they got early kills against bandits, and hit level 4 quickly. Thus giving them more chance against further bandits, and increasing the chances of being able to keep those jerks from actually escaping their forts. Though I think this particular tactic might be a bit easier on a large map.... as it's hard for red and blue to also get kills VS each other on this tiny map (which is also important on Hard) when bandit keeps are directly in the way.... but it still worked out to hold them off for a time and generate some units on each side that were pretty powerful.
Another thing that really helped here was Nemean Lion. That's a very effective token! Even if level 1 units grab it, it's still useful. They're bound to get a couple of bandit kills REALLY fast after grabbing it, so they'll level-up immediately, particularly if you used it in the right spot. Important to remember that like any token that works on units it can be grabbed by either side!
I think it wasnt until nearly turn 15 or so that I started to try to get siege units going on either side. I mighta started earlier, but I also had the Divine Summons woe approaching, and used Pandora's Box to speed it up since it was going to take 15 turns to get there. Pandora's is also useful if there's alot of mountains around as it makes for units that can chase escaping bandits through those mountains. But of course, the triple-speed woes aspect of it is dangerous.
Also ranged units, both human, and mythological (if you can get any out during this time; I'm typically slow to start that up based on my playstyle) are great at picking off new bandits to get kills and thus levels without worrying about counter damage, which can be a major problem for any melee unit attacking a keep.
There's probably more tips I could give, but those are the ones that I can remember. There's been lots of destruction in my current game so far, 1 red city got utterly flattened when the blasted Spies woe went off and another red one got half-flattened because a bandit siege unit managed to escape and go bonkers, but currently I still now have 3 cities on each side and not TOO much lunacy going on. Pretty confident I should hit the age of monsters without major trouble now that that initial storm was survived.