To improve pathfinding performance and reduce passenger walk times, how about a travelator?
The travelator for now could be bidirectional and have a fixed length (say 8 foundation tiles/32 wall tiles).
Pathfinding should become easier because a farly large share of passengers (>90%) would only be routed from travelator to travelator until they step off the travelator that is nearest to the gate they have to take. You could just cache a few routes from the nearest travelators to the usual targets (boarding desks, security exits) and from the usual sources (security checkpoints, gates) to the nearest travelators, and then routes from travelator to travelator. That way, a now 80 tile (320 hops) way around the terminal could become a twenty-hop path.
Btw, my favourite picture regarding pathfinding performance, showing about 100 contractors waiting for pathfinding:
