I agree with jhhowell. It seemed like I faced endless and endless stacks of Grey Death. After around 10-15 enemy FM's slain their military seemed to decline and I was able to push south and East.

As far as sauromate is concerned, you can go neutral and ally them in the first few turns. I have not experienced them break the alliance, even on VH/M.

Use the terraine to your advantage.