Regarding turn times: I think it would be possible to make AI use the time during the player's turn for thinking. Sure, some units might get repositioned and the pure tactics would have to occur during the AI's turn, but couldn't the whole strategic layer be moved to the player's turn (which is taking several minutes more often than not). Also "peaceful" decisions like which tiles to improve, which cities to convert etc. could be handled during that time. Wouldn't this be a possible solution? (It's a genuine question. I don't know much about programming, but this is the first thing that comes to mind when I read about how turn times pose a limit on the AI quality).