I love the idea of different types of roads with significant costs associated with the best. At first, all roads should just be regular dirt paths. These could be upgraded to be wider, compacted better, etc. In the middle you could have cobblestone roads, and at the upper end you could have actual stone-paved roads. Stone-paved highways, while conferring very large bonuses to speed and possible defense, should be major undertakings. I like the idea of making roads a strategic aspect of the game. It would be very, very expensive to make all your roads the best that you can, so you'd have to choose the most important routes and focus on them. This would make the world and empires feel more organic and more real, and make the player think about which routes are the most important (instead of just paving over everything because you can).
That's all separate from magic, of course. Through magic you should be able to achieve more or less the same affects as through 'mundane' roads, and then some. But again, if you want to create the magical equivalent of a stone-paved highway, the cost shouldn't be trivial. You should also be able to improve your entire road network as a whole by a little but, but also to focus on specific routes.
If there are weather effects (and if there are I would prefer that it was simply raining, sunny, snowy worldwide rather than emulating weather patterns) then units travelling on dirt roads could get bogged down, while those on stone roads would not... just a thought.
Weather affecting roads would be neat! It also lets you weather-proof roads with magic. And, even though this isn't the main topic of the thread, I would love weather patterns vs. global weather).
