Horsemen (from the King's Tent) are far and away the toughest unit available from level 1 (even if it is a pathfinding exploit), but Sprites will be worth their weight in gold as soon you complete the Anga's Ruby quest in Freedom Islands. I think it is +3 morale, +3 damage and +3 movement? You can't beat that. Works on Lake Fairies and Demonesses too.
