Why have all wandering "monsters" be bad. Why not have some helpful or interesting encounters.
Wandering faeries: They wander around for a bit and then disappear if approached they have a number of things they can do such as enchant or hex a unit, preferring to enchant/hex heroes.
Wandering trader: Can sell you an item/creature, could buy or request an item/creature, or could be an ambush of bandits hiding in that caravan.
Little rare creatures: Though whimpy these little guys are worth quite a bit of gold/mana/research if captured or killed, they stay away from troops however.