Could work your way into an invasion scenario. From you are describing having the equavilent of Romans invading could be intriguing. Even just a single legion. Initially you have scouts and vanguard outposts of a strange race/culture popping up and searching places they are not meant to enter. As they establish forts and a foothold on the lands, the tribes of humanoids are displaced and encroach on the pc's territory. Eventually the privelaged and wealthy bored general of the invasion force begins full scale attacks on communities and the players spearhead an insurgency.

Romans is just the basis for the force, could be drow, or a race that fell from prominence ages ago and is now returning.

As the foreign influences grow the sense of nationalism or tribalism in regions grows leading to smaller scale King Arthur types that the group can assist or oppose. Tie in events to the ancestry of the lands,so that relics of symbolic nature or mystical power are more than mcguffins but integral parts of rallying the locals or opposing the invaders.