With the new version loaded, I tested your scenario again - it took me 6.5 hours with some aggressive expansion. I have some remarks/suggestions:
Dismantling defective buildings to get your first building materials: great idea. For the quarries and fishers it's clear why they should be demolished, but for the wells/lumberjack's houses Amalea could explain that they're inefficient? That would make the objective look less random. Reduced productivity (percentage shown on building) is only clear after a few minutes, and there's also enough building space available, so maybe you could remove the farms from this objective (and from the numerous initial talks)? By the way, dismantling a custom lumberjack's house still returns an ax, that looks a bit weird.
For the farm plans: you could scroll to the artifact before you remove it.
The road network: it's certainly not as crappy as what the AI sometimes comes up with in a long game, but I understand it's not easy to invent something worse. I did make a patch (I'll attach it to bug #1705950) that places carriers on the roads and recruits in the barracks, because they should be there when Lutius & Co. arrive in Fremil. Concerning the objective, it may be unclear to players when it is fulfilled. I took a peek at the code, but otherwise it's hard to tell when the road network is "cleaned up".
For some time, I missed the start for the 'heroes' objective because I just continued using the low-capacity training camp.
The new enemy_seen function gave an error: "scroll_to_field(en_see) Expected a userdata, but got something else.". I had a look at the code but I didn't understand what's wrong.
After a goal is cleared, let character specify which one is done. That would help (at least for me) to keep track of objectives.
Difficulty depends on AI indeed. You could help the poor Barbarians a little bit by disabling shipyard/weaving mill for them.
About the narrative: In the beginning someone remarks it's "great to see the city walls again", but city walls are entirely alien to Widelands... Change to "the great mother city" or "the industrial core of the Empire" or something? Furthermore, as of now our heroes re-enter their homeland, but there's no context. Maybe introduce a new character, a servant/governor that bids them welcome and explains something about the situation - without revealing all there is to know? That could tie in with some of Nordfriese's suggestions. I was thinking of an evil usurpator, only interested in short term riches, that struck a dishonourable deal with the Barbarians: a part of Fremil in exchange for (temporary) peace. Maybe he banished the Vestal priestesses? This usurpator flees the scene when Lutius arrives, of course, so maybe they could meet later on.
Suddenly I think of something: where's the Emperor in all this?
Extra talk for Lutius: he could recognise certain landmarks near Barbarians, or maybe a captured Imperial fortress.
On religion: Maybe you could use different names for the gods? So they could be not exactly Roman, but inspired by history, as the imperial tribe in Widelands very much is. Vesta's punishment: burning lumberjack's homes is a nuissance rather than a pain. You could set fire to an armour smithie for a change.
Last remark: in your scripts, you're mixing tabs and spaces. Could you stick to only spaces?
Whoa, what a wall of text... Anyway, your scenario is really innovative, thank you for it!