I posted it in another thread, but I think it would be cool if migrants/traders/invaders would sail in from the edge of the map. The difficulty and frequency could be tied to some metrics relating to the players advancement. You could have multiple factions, possibly tied to the direction they came from, so some might just send trade envoys and be friendly while others might launch invasions. Some may just attempt to colonize unclaimed areas and be largely neutral.
Obviously this would all have to wait until the boat and diplomacy updates, but I think it could really add a lot to the end game.