How about something as simple as this. There's a tab in the city screen that lets you choose trading partners for the city. When you found a new city, it automatically gets added to the list in it's possible trading partner cities and a caravan unit starts to try to make it's way there. When it arrives unmolested a level 1 road is built along the path taken by the trader. If a monster or a hostile player interrupts the caravan unit, then no road is built. That way, a safe path bereft of bandits and monsters will lead to a road being built fairly quickly and easily, not to mention naturally\organically, while a monster infested region requires an escort\ranger group to clear it first.
As more caravans start to go back and forth the road gains in levels, say after 10 trips to and fro it becomes a brick road, and after 50 trips it becomes a roman highway, it might be an idea to have a research requirement for the roads aswell. The roads most used in trade grow the fastest, and the most natural paths with the least amount of obstacles grow naturally to become the most effective and used roads in your empire. No hassle. Heck, there might be no reason to even have the aforementioned tab, why not just make the whole process automatic? When a city is started it automatically starts trading with it's neighbours and a script determines what path the trader unit should take based on previous enclaves and the roads connecting them, not to mention the state of those roads.
If we want to make it even more complicated, the pathing of the traders should adapt as the terrain shifts and forests are cut down and grow up, mountains are leveled and raised and so forth. What i mean is, if a road is not crossed by a trader for a number of turns, the parts of the road that was not traversed starts to degrade in level, until it eventually disappears back into nature. Imagine a road between two cities separated by a local mountain range. The two cities have a trading relationship for 50 turns and the road between them is traversed by a number of traders based on the improvements in the two cities and the size of the two cities. The amount of trade on the road, and on all parts of the road determines the general state of the road. This doesnt need to be too complicated, it just needs to be able to adapt to new road conditions. Say a channeler lowers the center part of the mountain range allowing for traders to pass through the newly created path between the mountain tops. The path the traders take should automatically calculate that it is faster and start using that instead. Eventually a new road is built there as more people travel it, and the road that circles the range falls into disrepair.
Uh. Didnt seem to be very simple at all, really. I guess i'll summarize the idea :
Let traders be fully automatic in what paths they take between cities and let trader numbers be determined by the improvements\size of the city. As traders travel a path, a road begins to form, one to and fro makes a dirt road, ten to and fro's make a paved one, so on. If a road falls into disuse or the ones using it frequently fall pray to banditry, then the road should start to decrease in level. As new cities are built, traders should update their paths, and as the map changes and paths are made and blocked, traders should update their paths. Fully organic roads with almost no micromanagement hassle and fairly visible mechanics.