Ok I figured out my problem.
The answer was in the profiling screenshot. The query “DetermineBestEnemyLineMelee” was insanely expensive, and being run very frequently, and I have to assume that this was blocking the other queries from completing within a reasonable timeframe.
This EQS query is used to determine which enemy is the most appropriate target to engage in melee (not necessarily the closest!). It generates a list of characters, and then was running some tests, including a pathfinding query to ensure the AI doesn’t try to charge an opponent that is unreachable. The pathfinding test was INSANELY expensive, being more expensive by itself than the ENTIRE EQS query to find a good place to deploy its soldiers. I have no idea why this was, but removing it resolved the problem.
Does anyone know how this test works? Is it just using synchronous, non-hierarchical queries? If so then that would explain why it’s so expensive…