This would be incredibly confusing. Units with different movement speeds have different sets of tiles they can and can't enter?
How do you include features like "double moves in forests" or "double moves in hills"?
How robust would such a system be, say to effects in mods (like FFH Haste or Slow spells) that changed movement speeds - and left units unable to move because they were too far from the enemy.
And you have to trace a pathfinding route to any particular tile to find out if you can reach it or not, with a given unit? From where do you trace the route?
What if a couple of new forests appear, that blocks the old pathfinding route you had; this could strand your unit.
Such a mechanic seems too complex to solve what is a fairly low priority design goal.
I think any hard-cap on where you can move your units is pretty un-fun. There are better ways to make exploration less trivial, by increasing danger of losing units to barbarians, and changing how/when map-trading works.
It wouldn't be the speed for Each unit but for a 'Standard infantry unit'....ie 2 hexes on land and X hexes on Water (after transportability over water is achieved).
So it wouldn't be different for a Cavalry and a Warrior.
It Would be different for different Terrains though.
So instead of a simple 'circle' around your cities it would be irregularly shaped... your 'limits' wouldn't extend as far into the forest as it would over grassland.
It wouldn't go over mountains. (assuming units can't go over mountains)
Admittedly, it would probably be better if Desert/Arctic took 'more moves' than Forests, but by making it depend on the actual 'movement cost' it keeps it simple
You could extend your borders in a certain direction by building roads in that direction (although it appears they may cut roads.. but the principle would hold). Rivers should extend it
It would basically be a second set of borders, you have
Cultural borders
Supply borders
and
Extended supply borders (Scouts)
And it would also change with technology
ie your "supply borders" wouldn't extend over 'ocean' until 'astronomy', certain techs would just increase the amounts (automobile, steam engines, social 'logistics' techs like bureaucracy)
The point is this mechanic wouldn't only affect Exploration, it would also affect Military. (and even settlers/workers... some limit on how far away those can be, but of course once they founded a city/built a fort that would extend the range.)
It essentially would be the border of where your supply lines reach.... some units could be on the 'long' supply line, some could even be off the supply line altogether.
.......................... Revised Idea................................................................
Perhaps just single "Supply border" (not invisible, based on a traceable line that gose at different distances over dfferent terrains, and is blocked by some, including enemy units?) that if you exit it causes
1. Inability to heal (advanced late game explorers could have a promotion to avoid this)
2. Massive increase in maintenance costs (advanced late game explorers could have a promotion to avoid this)
3. Decrease in combat Strength?
Then add Inability to move into 'hostile'* tiles (including for the supply border)
*possible definitions for hostile tiles
Tiles that are
Outside cultural borders
AND
Jungle/Desert/Tundra/Hill terrain
Have Each (Desert/Jungle/Tundra/Hill) have a separate 'promotion'.. or perhaps 2 promotions
1 promotion lets you enter the 'edge' (so that you can enter tiles of that terrain as long as they are adjacent to a tile that is not hostile.. water/grass/plains/forest)
promotion level 2 lets you enter the 'interior' (that terrain is not considered hostile to you)
So Hannibal can get his 'hill promoted elephants' (hills normally considered hostile terrain for elephants. catapults and such, most other units would normally have the level 2 'hill' promotion)