I played the game with Egypt and Ethiopia on emperor difficulty. I decided to write down my experiences in the form of strategy guides. The guides will probably be a bit too specific, but I don't want to speculate too much. Also I'm not a great player. So any additions or corrections to the guides are welcome. Here they are:
The lands at your disposal are fertile, but not very productive. To balance this however, you have two great UU's at your disposal. It would be foolish not to make full advantage of them, so prepare for some desert warfare!
Your first task, the usual exploring and making contacts, is pretty limited. Suez is blocked, and there is mainly desert to explore. Send a warrior to Carthage through the desert. If you make him follow the coastline, he won't survive. As a bonus you can get the two goody huts there, potentially giving you somewhat advanced techs.
The next task is founding a second city. A good choice would be one tile south west of the goody hut between you and Ethiopia. Build a monument there so you can grab the best tiles, and push back the cultural borders of Ethiopia. These two cities should be sufficient for the Egyptian war machine. When your borders engulf the horses in the north, start producing chariots. Their enslave capability, together with the industrious trait, allows you to create and maintain a larger army. Use them to kill some barbarians, while you wait for your army to grow strong enough. Add some cheap axemen to the mix when available.
Before you start your conquest, it is best you switch to monarchy first. You may try getting it as bonus tech from filosophy; you probably are at the head of the tech race through huts and trading. Don't acquire mounted combat too soon, because you won't be able to make chariots anymore.
When your army is about twenty strong, it's time for some major expansion. Your best choice to start would be Arabia, though you may want to eliminate the Hebrews first, because they will not allow you to move through their land without a ROP agreement. When your golden age commences, Egypt is suddenly transformed into a productive power. Use this advantage to build more troops to continue your campaign. Even Persian immortals will offer little resistance to your might.
There are two limits to how far you can go: the OCN and the Middle Ages. The first you will hit quite fast. It shouldn't be hard to get a leader out of one of your victories. Both Persepolis or the Ottoman capital Sogut are productive power houses, and are good locations to rush build the Forbidden Palace. Later on, you can build the India Trading Company in the other one. By the time the second limit is reached, your conquest will probably already have ended.
Natural borders are nice to defend your empire later on, and thus a good indication to end your expansion in that direction. The mountains to the north and east of Persia, the mountains of Caucasus in the north and Byzantium in the north west are logical choices. In the west you may want to conquer Carthage for easy control of Gibraltar. Stay out of Ethiopia, there is nothing for you there. They are close, but conquering them will increase corruption throughout your empire even more.
By the time you enter the Middle Ages, you are potentially world leader in about everything. The Islam wonders are yours, and with easy acces to spices, so is the important India Trading Company. Your position provides you with lots of resources to trade, so much you probably won't get rid of everything.
Cultural victory is extremely viable as you're religious, and you will have lots of gold to rush improvements. If you have patience, domination or a spaceship victory shouldn't be too hard as well.
As Ethiopia, your main battle will be against the land itself. Luckily you're agricultural, which helps. Too bad it doesn't make granaries a little cheaper too...
The first choice you'll have to make, is whether you're ready to settle down. If you don't mind a little loss of historicity, moving your settler one tile to the planes in the west, will give your capital larger potential. You can capture Egypt's worker with one of your first warriors, so you won't have to build one immediately yourself. Send a warrior to Carthage and grab it's goody huts. After a short while, the barbarians in the west will come over to play. They are quite harmles however, unless threatened. So simply block them off with some warriors until you can make a catapult to throw stones at them, forcing them to retreat.
Your next city will be up north, as barbarians still hold the west. The third city goes on the plains near the east coast, or maybe further south near the horses. The first position may seem quite bad, but it offers some production and your ships will be safe from barbarians. Ships? Well...
As your land offers little production, conquering nearby Arabia is a good idea. And it's best to do so as fast as possible, before they grow too strong. Go for the sailing tech, and trade for other important techs. Because you won't have horses early on, catapults are a nice addition to your army. Upgrade your warriors to spearmen; you need every man you can get. You may consider calling in the help of the Hebrews. Their maccabees can kill some of Mecca's defenders, and additionally trigger Israel's golden age, helping them to produce Temple Mount. Which you, of course, will capture later on.
By now, the nations of the Middle East have filled up their natural expansion space. So they will all be heading your way, to claim central and west Africa. You can take advantage of this by picking off settlers from nations you can afford going to war with. Each settler you capture gives you three much needed slaves. Egypt will be your favourite supplier, until you decide to destroy them. The next target is Israel. Their position allows for acces to the Mediterranian, provides additional salpeter, and - if all goes well - Temple Mount.
In one of these wars you can trigger your golden age with an Oromo horseman. This first UU is somewhat cheap, and it's blitzing capability may prove useful. By the time you get chivalry, you've probably gotten behind in tech. Use your golden age to catch up, and to build the infrastructure needed to stay at the head of the race. Make sure you already have libraries in at least your top cities before you trigger it though. By choosing and trading your techs wisely, you will find yourself back at the top by the time your golden age ends.
To make best use of your native land, you should cut all forests to reveal normal plains, and plant new forests on the LM ones. Later on, clear all marches and cut the jungle. Expect it to take a while. It's not all bad though. There are sufficient resources at your disposal to make some money. Also, the India Trading Company is within reach because of easy acces to spices. What you don't have, is coal and iron. These can be traded for, or you can take both from the Zulu's with a single city. Don't underestimate the Zulu's, they have strength in numbers!
Your second UU, the shifta, is rather unimpressive. You should have enough gold to upgrade to and support better units than that. But if you for some reason plan to unite Africa, they might be of use.
As for actual victory conditions, a diplomatic victory is probably your best bet, if it can satisfy you.
That's it, I hope they are useful
In my Egypt game I reached 35k, but the game didn't end. I vaguely recall culture also needing to be relatively big, so I suppose I need double the amount of my closest competitor. In this case, it was Japan with 19k. I didn't really think about victory conditions early in the game, so I started pushing culture too late. I could still reach it, but my patience was running out.
I was getting techs at the maximum rate, with my sience allocation only 30%. Yet the only lead I had over the other advanced nations was through the Ecyclopedia wonder. I captured the top cities of the worlds second strongest nation, Germany, and started razing the rest with my new tanks. I did the same to other nations that dared to challenge me. In other words I got bored
As for Ethiopia, I was plagued with a broken reputation and had no idea why. The first time was when declaring war on Babylon. I had no deals going with them, and no trade routes went through their land. I simply went back a save, and waited. At some point, declaring war was without consequences.
The second time was right after a peace treaty with the Zulu's. They were still coming towards my most southern, poorly defended, city. So I asked them to leave or declare war, so I could bombard them from the sea. They declared war, and next time I checked diplomacy, my reputation was broken again. When asking peace I got a city from them which I gave to some other weak nation, but that seems even less likely to have been the cause. I've had it
A final remark:
I tried democratic republic and constitutional monarchy, but they don't seem to give any further reduction of corruption over oligarchic republic. I waited a few turns, but no noticable improvement... In my first game I had about 25 cities, in the second 15. I had India Trading Company in both.
What is the optimal city number anyway? And how much is added by the forbidden palace and the India Trading Company?