From your post about the troops beginning to move, it sounds like the game/ai calculations are the issue, but the pause test will prove that.I have not tried pausing the game to see if FPS goes back up on those machines, but will find out. I tried it on my machine with the saved copy of the game we played last night and I went from 45-168. Least it will narrow down what we are looking for.
I have a decent machine (i5 @4ghz, 16gb ram) and when I run a ~30,000 man battle with AI, I get ~10 FPS. Pausing the game gives me 60 FPS, so it's obviously the game/ai calculations in that case.
Of course, if I play one of the maps with huge wheatfields like McPherson, and look at all the wheat at once, my FPS drops really low just from that, and pausing has no effect.
Performance varies hugely depending on what exactly you are doing.