Ok, the code is mostly done and working, although I'm still checking details.
The formula goes like this: there's a base radius (for the moment it's set to 3, you can set it via xml). It's scaled for mapsize (+1 for mapsize, so it's +0 for Duel, +1 for Tiny, +2 for Small, +3 for Normal and so on). On a Normal map the starting radius is 6. Then it's scaled for Era, 6 is in Ancient Era on a Normal map. The radius is centered on the closest city of your civilization. But I still have some doubts on how to scale the radius for era; scaling should be done for Ancient, Classical and Medieval. When Renaissance begin, you should be able to roam freely. Additionally, you can freely roam inside other civs territory if you have Open Borders and you can always follow paths/roads even if the plots are outside your radius.
The problem I see with your proposal is that Cartography and especially Colonialism come very late. Colonialism is halfway through Renaissance when you're supposed to roam freely already. I could make it so that Cartography doubles the radius and Colonialism removes it completely. Also you could remove the radius completely when reaching industrial instead of renaissance.
So on a Normal map you would start with radius 6 on Ancient; for later Eras I'm experimenting with +3*Era radius, so it would be 6 on Ancient, 9 on Classical, 12 on Medieval. It could then become 24 when hitting Cartography and no movement limits when reaching Colonialism OR Industrial Era.
What do you think? Other suggestions?