I definitely find that CiV gets much easier the slower the game speed because of human military superiority. On normal speed if I wipe out the AIs army they will replenish it in 15 turns - I might not get to take more than 1 city, or maybe none at all if the distance is substantial. On Marathon it takes them 45 turns to replenish their army which is enough time to conquer their entire empire. Given enough time to reposition and juke around a skilled human can beat any number of AI units which is why the faster the game the harder it is because you can't afford to take an entire era to capture a single city! The less time you have the more risks you have to take.
I don't see any way around this though, it is just a function of having more time to play with. That is, of course, unless the tactical AI can be made as good as an expert player... also, I would like a pony.