"Ridiculously complex" is a bit of an overstatement. None of the code is super easy but there's nothing too unexpected - except for unitMotion maybe.
The pathfinder is actually 5 components:
The obstruction manager handles collisions (for unitMotion - not the pathfinder proper) and rasterising static obstacles (like buildings and terrain) and keeping track of units.
UnitMotion handles the actual movement logic. It's terribly written at the moment (buggy, unclear and inefficient at actually moving sanely…) and I have a patch (I think it's D13) fixing it. On top of that, we need to change the architecture to a Data-oriented design - I may or may not have a patch for this, can't recall, but I've definitely done it somewhere.
The hierarchical pathfinder handles accessibility (and could be used to handle high-level pathfinding, but it's not really much faster). It creates big "regions" and connects them. That's where flood-fill comes in. I have a patch (D53 I think) that improves its performance.
The "long-range pathfinder", AKA the A* JPS pathfinder, is pretty well optimised (aka making it much faster would take too much work). It can create a path from navcell A to navcell B using the rasterised map of the obstruction manager - so no unit avoidance here.
The "short-range pathfinder", aka the vertex pathfinder, aka a graph pathfinder, is used to walk around units. It's triggered by unitMotion when getting stuck in some special circumstances. It creates on-demand an exact map of all units and A* on that.
Nothing is threaded right now but two things are 'easily' threaded: the long and short paths computations. These are currently done between turns, and could be parallelised. Doing it _super_ safely would mean rewriting some stuff, doing it kinda dangerously is very easy and I have a patch for it on Phabricator somewhere.
I also have (this one indeed very WIP) patch for unit-pushing, which removes most of the need for the short-range pathfinder (it's still useful to keep around for stuff such as finding your way around a resource).
The short-range pathfinder might be optimised for the common-is case of several units close together since we could reuse the graphs across computations if those are in the same region - but it's not trivial to do correctly.
The other patches are pretty much finished and ready to merge, they just need some review and some more testing.