Emperor is about as high as you can go without using exploits, fudging the map, or map dependent. Maybe one after but deity you have to be aggressive or map dependent. Did you more or less have to do island naps and micro your ass off. It's not fun.
Over the past couple of years (since trying to move up to DemiGod) I've pretty much come to this conclusion as well.
I usually choose the map-size but let the pRNGods choose all the other parameters (everything set to Random), including my own tribe. Nonetheless, with even just a half-decent start, I can usually beat the Civ3 AI up to Emperor, but every single (nearly-)all-Random DG game I've started to date has ended in defeat, and usually sooner rather than later.
(Fastest loss so far was getting stomped by Iroquois Axes on Turn 20: my nearly unguarded capital would have reached Pop3 that turn, and finished building my first Settler...).
I have been trying to beat Conquests Japan on Emperor, and now it seems the best idea is to literally take a sheet of paper and draw where the key resources are - iron, horses, jade.
Even though Yamabushi are (way) OP, this scenario is one of my favorites of the Firaxis-offerings, because it gives me full freedom to plan my development (unlike the scenarios which force crowded/ crappy starting-positions on the player). But yeah, if you don't start with one of the few tribes, e.g. the Takeda, or the Mori, who have those resources closer to their own spawn-point than their neighbours', then you need to build a stack of Stone Crossbows to go and secure them ASAP, because this scenario cannot be won without Iron
and Horses.
Jade I've found to be less vital, because by the time I can build Ninja, the AI-tribes will likely have upgraded to at least Shogun-5 or -6 (thus requiring 4-5 Ninja for each assassination attempt, just to have a reasonable chance of success). Despite that, beelining to Ninjutsu during the Middle period is pretty much key to winning this at the higher levels -- not because of Ninja, but because the AI-tribes almost invariably pursue the Bushido-beeline instead. So going the other way gets you Philosophy (+ 2 free techs) and Diplomacy, meaning you have a good shot at (pre)building the War Council -- which just like the epic-game UN, you have to build (or capture the city where it's built ASAP), otherwise you risk losing to a surprise vote.
Also, if you get the Yamabushi-tech (Bojutsu?) before your neighbours, don't share it until you've planted your own Yamas (or Samurai-Spears, or -Arquebusiers) on at least one of each of your Strat- and Lux-resources. After that, it's safe to let the AIs have it, and watch them pillage away all of their rivals' resource-tiles...
