Regarding the AI difficulty levels, I think that what is the most challenging for a beginner is to develop faster than the AI, or at least fast enough to survive the first attacks. Thus, what about decreasing the rate at which the AI develops its economy (e.g. builds new units, builds new buildings, harvest...) to lower the difficulty of the first levels ? Also, what about increasing the "grace period" before the AI first attack ? These propositions have the advantage to keep all features of the game while making the game significantly easier.