I **think** that a large proportion of the game slowdown caused by Civ Shipping Lines is caused specifically by Civ ships looking for a route to take but failing to find one.
When a civ ship can not find a route to take, the ship sits idle and checks for a route again in the next increment.
If all civ ships are busy and then one fails to find a route, chances are that more ships will fail to find routes as they finish their current runs.
If a large number of civ ships are all checking for routes in every increment, and if the route-checking algorithm takes non-trivial processing time, then we end up with a big chunk of processing time being used for this during every increment.
Anecdotally, I notice that civ colony ships are idle far more often than freighters. This is true for my own empires, and also for NPRs (on the occasions that I have needed to examine them).
Suggestion:
In the code that checks for available routes for civ colony ships, if a ship fails to find a route, skip the check for any other idle ships at the same location and of the same or larger size.
Assuming that you are correct about this logic (and Steve only knows for sure), I wonder if it might make sense to shift from civilian ship-based logic to contract-based logic.
That is, instead of each civilian ship looking for a contract or job to fulfill, each contract or job looks for an available civilian ship to fulfill it (here, a "job" includes non-contract things civilian shipping can handle such as trade and automatically moving colonists). If there are no jobs, then civilian shipping remains idle.
I suggest this in part because the way contracts work is a bit odd, since the civilian logic will usually fulfill only one contract at a time. If I have infrastructure delivery contracts set up for 3 different colonies, for example, the civilians will prioritize filling one colony at a time when I might prefer an even distribution. Job-based logic would allow cycling through available contracts to achieve this.
That said, the upcoming 2.6 changes to civilian shipping might eliminate these issues anyways for all I know, so this all may be unnecessary speculation.