I don't think the terrain point is a thing. The game could do the maths which I can't imagine would be that hard. From the players POV, you'd just have various city names in the city purchase screen (maybe at the bottom under units etc), each with a gold cost. Press the button, gold gets debited, and you get a road between those cities.
Building a road for war is more of an issue. I mean, I often do that already using traders. One solution would just be that you can only build roads between foreign cities if your allies - or with city states only if you have at least 6 envoys.