The simplest way would be to add a fixed Trailblazer penalty to each terrain type, that you pay no mater wich road/rail you are putting there first.
For upgrades, following the existing road would be inherently the cheapest way - no additional trailblazer penalty.
If it stays at a percentile modifier, chances are really good that going the originally cheaper way would be cheaper even with the Upgrade.
This makes the most sense to me, since to build any kind of road or rail through terrain the first time should naturally account for modifying the terrain if required (e.g. building bridges, tunnels, etc.). It would mostly make sense for this initial "trailblazer" fee to be mostly waived for future roads.
However, I say "mostly" because IMO there should still be some terrain modifier applying in less-than-ideal terrain - e.g. there might already be a dirt road with a bridge there, but one would expect a paved road to be larger and any bridge it traverses to be much sturdier (e.g. to handle heavier loads, not wear out as fast, etc. since paved roads allow more more Logistics points, therefore it's implied there's more traffic).
But in general, the largest fee should be for the first road through difficult terrain - IMO it's a fair tradeoff of realism vs. gameplay/QOL and potentially reduces/eliminates issues with automatic road creation.