There's also the question of turn timers. In the late game 12 Civ games on high difficulties have turn transitions of 1 min+. Imagine if the AI actually had to calculate the best move for all their military units.
I have a suspicion that this is in fact the biggest reason for the stupid combat AI.
You are correct for the most part: besides Great Works swapping, almost all algorithms that I know of that prolong AI turns are related to the pathfinder, and Great Works swapping is only slow because it is implemented
extremely poorly, as in it contains rookie C++ mistakes (mistakes that you'd expect from a university student); it was probably programmed by someone who is more comfortable with Lua than with C++, hence the usage of stuff that's common in Lua but is unnecessarily complicated for C++.
The pathfinder is... well... it's slow because it is extremely thorough, very exact, and completely serial (ie. none of its algorithms can run in parallel, so the program is forced to go through all the steps one at a time using, usually using only one core). After all, you can't have the AI moving a unit in a way that a human player wouldn't be allowed to. Heck, just try switching to Strategic View (to avoid framerate slowdown caused by graphics), select a unit, hold down the right mouse button, and just move your mouse in giant circles on the screen: each time your mouse hovers over a different tile, the game's pathfinder needs to check what the shortest route is to that tile using the unit you selected. For me, the result is a drop from roughly 120 FPS to 100 FPS if I move my mouse quick enough, though this is with AuI's pathfinder performance improvements (a few of which were borrowed from the Community Patch Project); without them, I can easily drop down to 80 or 70 FPS. Since every AI, even the city states, needs to run possibly thousands of pathfinder checks each turn depending on how many units are in play, long turns are inevitable as the game progresses and the AI has to keep track of more and more units, allies and enemies alike.
Fixing it is not impossible, but it would be time consuming. Having worked with Civ5's pathfinder code a lot for my mod, I can safely say that not even Firaxis has a clear idea of how its pathfinder works, as proven by odd code bits of data being cached and then never used, or successive steps performing the same, expensive calculations again and again with only slight modifications each time. I've messed around with trying to allow for multithreading of the "what neighboring tiles can I move to?" code using OpenMP, but the game acted strangely each time, so I've shelved my plans for now. If anyone with the knowhow and/or the patience to implement C++ multithreading is interested though, I'll be happy to help them get acquainted with Civ5's pathfinder.
