Capture and keep the Grand Pyramid wonders in Egypt. They increase province loyalty, by about 40 percent if I remember correctly. They're in Middle Eqypt, just south of the Nile Delta. You can capture the Alexandria lighthouse wonder on the way. I don't remember what that one does.

Whole lot easier said than done.