Depends on who you want to start as. With Abyssinia or Axum, you can realistically start in 1066 and survive with good, aggressive gameplay. With Nubia... well, I suppose its possible in 1066, but the amount of pure luck needed is staggering, and 1076 is a much better start date. The Fatimids still have the power to steamroll you without breaking a sweat, but they're small enough that you can realistically build the manpower/alliances to defend against them (even then, it took me about five tries to get a game rolling with them... then on the last try, the Fatimids started off trying to push west, and the Seljuks then stomped them a little).
But if you wanna be an Ethiopian, the Zagwe Kings of Abyssinia is the easiest choice. Take Harer in a holy war, convince Axum to vassalize, and try to snag the last de jure part of Nubia. Then you can start pushing into Arabia, and with any luck the Fatimids will remain busy. If they get into any truly serious wars, just holy war them from the south. Taking the Duchies of Cairo and Damietta will do some serious damage to their levy numbers and their economy, as can Alexandria to a lesser extent (but its also what you need to restore the Coptic Pope).