When I heard about this, the map expansion feature, a mod for Civ V came to my mind:
Growing fog of war. This mod of course does not do what this feature does. But FOW grows back depending on the distant to your borders, techs and improvements/buildings.
As of how the new feature would work, I like your suggestion that you can only travel so far from borders you control. Maybe combine that with FOW growing back in earlier eras, that would motivate to explore the whole map in stages.