Just a little amendment, evidence of settlement at present-day Wiesbaden dates back to the Neolithic era (from
wikipedia).
Probably a kind of early sacred place that became this natural sanctuary place.
When they were digging the foundations for the museum in Wiesbaden they discovered a Neolithic tomb/burial - which they left in place, and organized the museum so that the basement level is Neolithic, followed by Roman/Germanic, followed by the Medieval German and 17th - 19th century Hessia-Nassau on the top floor.
Indeed. It's like non-aggressive nomads are missing; but what would it contribute to game, having them wandering on map - I guess they've been rationalized into plain yields.
The addition, I think, would be another potential 'source' for Mercenaries to be hired and Trade Partners for Strategic and Luxury/Amenity Resources. This, in turn, would allow the game to rationalize the entire Trade system so that all trade routes are subject to map effects - distances, geography. They aren't now (trade between Civ's in Resources is, essentially, Magical in that it can be over any distance and through any geographic features and borders). If you can potentially get Horses from a Barbarian Camp 15 tiles away, there's no reason to have Fantasy Trade Routes.
And I would maintain the 'Camps' as markers for Where The Barbarians Are instead of having wandering groups and a new 'barbarians mechanic' in the game. The difference is that a Camp could be Hostile (current Barbarian Mode), Friendly (current Goodie Hut Mode, except that it doesn't disappear when contacted, and can become, potentially, a Trade Partner, Mercenary Source, or other Bonus Source) or Neutral - which means it has to be persuaded, fought, or otherwise dealt with.
I think such a system would add to the variety of early interactions, keep 'Barbarians' relevant until much later in the game, and give you more uses for Envoys and Recon Units and even Great People, all of which should be able to promote better relations with the 'Barbarians'.
However, there's "allways" been paths between some locations - could be animals wandering to new grazing/browsing/hunting land (or to and off cliffs if they were lemmings) or human nomads doing pretty much the same and then gathering at junctions to trade - and eventually some of those trails better had to be upgraded to roads to carry the weight of all goods.
I think within your own borders, your units should basically move faster (at least slightly) - we're talking about claimed land and there you (should) know all paths.
I'm also for letting builders spend charges to put down roads on map, within their civ's borders.
Case in Point: the Native Americans had 'roads' everywhere in North America - regular routes taken by people, animals and goods between settled areas - but because they weren't wheeled routes the Europeans didn't recognize them and kept calling North America a "Trackless Wilderness".
A Movement Bonus within a radius or border of yours makes sense as a start to be augmented by 'regular' roads later. It might originally simply be better movement through terrain that normally impedes movement, such as having Civilian and Recon ("Unencumbered") units be able to ignore Hills for movement. Leaving out military units that necessarily include larger numbers, weapons, armor, food and supplies would keep the effect from being OP early in the game.