Someone will be along shortly who can answer this definitively, meanwhile I'll take a stab at it. Once a dirt road is built you can come back (assuming you've got the resources needed to do it) and upgrade to a surfaced road.

Yeah, it's a fairly late-game technology. (I think it is called Surfaced Roads.) Once you research it, then you can do the above ^.

I wonder, if you go with research tree mixed and you get dirt roads earlier than usual do surfaced roads come along contemporaneously?

The manual says it follows a logical sequence meaning for example you wouldn't expect to get surfaced roads before dirt roads but does that also imply that if you get one of the precursor technologies early you might then also get the follow on technology early too?

You get dirt roads really early on, even with mixed research. Most factions start with it unlocked.

I believe each tech has an independent factor which determines how late it shows up in the tech tree. Randomizing the tech tree flips around the prerequisites, but the late techs still show up late.