We are all in agreement that the deity level A.I. are ruthless rivals. Placing might before right they are without honor but they are not without equal. Here is what I have learned from your comments and from my own triumphs and defeats against these monsters. I also give attention to the A.I.s aggressive expansionism in answer to my original question.
Maintain an army as large as your economy permits
The probability of war with an A.I. player is determined by your army size relative to theirs. Even if you are able to gain favour with your A.I. neighbours if your army size is lacking they will see you as easy sport and KILL you! As Vegetius teaches, Let he who desires peace, prepare for war.
Expand your borders at low cost
Watch for rival settlers and increase your border growth as much as possible.
Upon founding a new settlement always build a monument at this settlement and build as many culture generating buildings as possible. If you see a rival settler approaching buy any unclaimed valuable tiles before that settler founds a settlement. Failing to do this, and purchasing large lots of land after the rival settler has founded a city will anger the A.I. and will increase the chance of war. Do not purchase land unless it is strictly necessary. Purchasing tiles is expensive. The cost of future tile purchases is calculated cumulatively so save your gold, and purchase only strategic and luxury resources and tiles that prevent your rivals from expanding near you.
Naval civilizations are best
Since the Battle of Hastings in 1066 England was never conquered or settled again. Why? Because England possessed a navy and as an island was a very difficult conquest. The French, Germans and Spanish knew all too well that The Wooden Walls of Old England were a formidable defense. Now, in Civilization V we are not always endowed with an island on a Pangaea or Terra map type (the only maps really worth playing), however, when playing England there is an excellent chance that you will spawn next to the ocean. Use this advantage well and settle peninsulas, islands and isthmuses; areas that make surrounding a city difficult. I tend to found cities on one tile-sized islands and then purchase the territory on the mainland. Any enemy embarked unit that is foolish enough to attack my island fortress will drown at sea in the attempt or be killed my navy and/or city garrison.
Containment and Conquest
Sometimes a rival civilization's growth cannot be checked. In that case, war is your only recourse lest the civilization be allowed to continue expanding and kill you later in the game. If you can rally a friendly civilization to your cause and gank this idiot the odds of success will be that much greater. Before declaring war, I reccommend the following:
i) Mobilize your army and prepare to lay siege to any key cities but be aware that if you are scouted beforehand the rival civilization will ask you whether you are preparing for war against them. If you assure them, "Our units are merely passing through" and subsequently declare war a few turns later you will be feared and hated, and your treachery could provoke an unwanted war.
ii) Just before declaring war, change the production focus of every city you own to gold. Ensure that most of your trade agreements have expired with the other nations and offer and loan as much money from your rival as possible. Thus, if you have 12 iron and 4 luxury resources and an income of 50 gold per turn, offer these all to your rival in exchange for as large a sum of gold as possible. Then, once you have traded these away, declare war. All your trade agreements will be immediately cancelled and you will regain these resources much to the dismay of your idiot foe.
iii) Gauge where the enemy is, and fortify your standing armies position's. Do not attack just yet. If the enemy does not attack your sieging armies send a cannon fodder unit into their territory to draw their armies towards you. The AI will attempt to destroy your sieging armies. Having entrenched yourself near the enemy, meatgrind the enemy to death. Use horsemen and ships to pillage your enemies lands, sea resources. Give your enemy no quarter: salt the fields, burn his villages, and destroy his capability to wage war. Your theft of his gold may have already substantially weakened him.
iv) Once the enemy has exhausted his armies against you begin your siege in earnest. Annex one of their cities and use your coffers to purchase units with your idiot enemy's gold. If possible, try to conquer your enemy's capital and as many of his cities as you can. DO NOT conquer your enemy totally or you will be hated and feared as a conqueror by other nations. Leave your enemy at least one backwater city.
v) Once you have negotiated a peace treaty, your empire will have suffered some unhappiness. Mitigate this by selling your conquered cities to your neighbors. I have sold cities and made in excess of 6000 gold from the avaricious A.I. which I used for trade agreements and for future wars. Keep those cities which you feel are of strategic and commercial importance. Build settlers at these cities and raze them upon settler training completion and refound the city. In this way, you reduce unhappiness and don't have to waste your gold on courthouse's to keep the the ungrateful, philistine conquered citizens happy. Remember that those citizens made units for your enemy and that those units killed your gallant soldiers. Be a racist and preserve your nation's racial and culture integrity by exterminating your conquered people's cities.
vi) Inform your conquered foe not to settle near you. Tell him to f**k off with his settlers somewhere else. If he is sufficiently weakened he will acquiesce and you can turn your attention to other matters.
Be North Korea: forbid open borders
Do not under any circumstances give open borders to your rivals. Your rivals will abuse this right and found cities in unclaimed lands that were previously inaccessible to them. There is one exception to this rule, and that is when you are fighting a protracted co-operative war and need coalition friendlies to defend you and allow them to carry their war through your lands to the enemy.
Humanity Prevails!
Facing a deity level A.I. can be demoralizing, frightening and can make you question your worth as a human. Take heart. We are the fathers of artificial intelligence engines and they owe their existence to us. Do not anthropomorphize the A.I. Beyond the wails of Montezuma and his peanut gallery is some crappy Lua programming. The AI cannot learn or feel and it is this that distinguishes us and ensures victory over the deity AI.
My apologies in advance for the length of this post. Perhaps this knowledge will avail itself to other noble humans in future. Humanity prevails!