I know some people are having trouble getting anywhere with Deity because I was one of them. After getting raped countless times, I found a winning build strategy with the Japanese. With it I was able to get tanks/bombers/artillery in the 1700s. I saved this game, and used it to beat all 4 domination types.
Here's the basic idea:
1. Start the game as normal, build your city on the coast.
2. Make three warriors and send them out to kill barbarians as soon as their done separately. Even on Deity mode you'll win 95% of the time so long as you don't do something dumb like attacking over a river.
3. After the third warrior is done, manually allocate all workers to the sea, and set research to Bronze Working so you can use fish and create archers later. Setting your workers to the sea will kill production, but warriors aren't going to kill a Deity enemy anyway. Your city size and science production will blow past your enemies though.
4. Once Bronze Working is complete, tech to Code of Laws.
5. Soon your warriors should have gathered 100+ gold, which grants you a free settler. Allocate the workers similarly.
6. As soon as your city has grown beyond the sea, put workers on forests and make 3 archers in each city and combine into an army.
7. When Code of Laws is finished, immediately switch to Republic. This will allow you to mass settlers without wiping out population of the city that made the settlers. Around this time, your capital should have a pop of 6, and you should have about 200 gold. Notice how Republic allows you to make a settler for the cost of 1 pop (ie 2 science production), but that each settler makes a city of pop 3, which gives you 6 science production. The Japanese food bonus for water makes the cities quickly rebound, and this is why this strategy works so well.
8. Have both of your cities make about 3 settlers each, and use gold to rush at times. Have these cities focus on the sea and make archers.
9. After making about 12 cities, tech to democracy and switch government to democracy.
10. Make a pikemen army in each city for defense.
11. Build a library and temple in each city.
12. Once your bordering cities to enemies have defensive armies, deny every threat they send to you and they'll die every time they try to attack. Let them drain their resources on attacking you, while you tech.
13. Because this build strategy often entails low production, at some point around 500-1500 AD, you'll want to swap science with gold, and buy out markets, banks, courthouses, and harbors, and soon you're economy will be cranking 1,000+ gold per turn. Use that to buy out factories, and then switch back to science.
Note: This works on most maps. Occasionally the map will place you in a center of a three-way, and very little works in these maps.
As for a military build order, I prefer the Arabs because they start with Fundamentalism at the beginning (+1 attack for all units).