Apparently there is a flawless strategy in civ5 and if you apply it correctly, winning on deity is rather easy. And you don't even have to make some special settings for the game. Just I have to warn that its much more fun if you discover it yourself rather than get it from internet, as in that way it kind of ruins your game experience as it did to me to some level.
The easiest way (as Irony Man correctly pointed out) is setting the map type to archipelago, as AI is totally hopeless on water. Just expand all the time, build some naval units to fend off any aggressive AIs, grab those resources, trade and develop. You should be able to get any kind of victory quite easily.
You can also use continents or Pangaea maps. You need to apply a flawless strategy to get a win on those. A strategy might be slightly different depending on which faction you are playing, but there are some basic rules which work for all of them. The specific faction strategy is to get the most of the special ability. That means if you are playing for English - build naval units, if you are playing for French - build a lot of small cities, if you are playing for Romans - build all that is needed in Rome, etc.
The most important bit is a good start. I would divide it into three phases:
- Settling. My winning initial build order is worker-settler-scout. Develop technologies needed to get those resources. Scout the land using your initial warrior and try to not be delayed by any spotted barbarians. Settle the land to grab the luxury resources asap, but don't go too far from your capital. Once you got a scout use it to discover map further and use your warrior to deal with barbarians near your cities. Get Liberty SP branch and Citizenship SP next. At this point you just build settlers, workers and monuments in all your cities. Forget about any early Wonders. If you met a militaristic CS you can steal a worker from them (they are useless). Declare a war, capture a worker and make peace all in the same turn. On the other hand its way too easy and some people call it an exploit, so I don't usually do that.
- Fighting. At some point you'll meet other civs. Be nice to them, but don't forget that they are your rivals and sadly due to a crazy inherent AI warmongering its almost impossible to make a good friend till the end of the game in Civ5. You might be able to settle 2 cities or maybe 5 cities (depending on the map) before you start rubbing your shoulders with other civs. Discover archery and build some 2-3 archers. Discover horseback riding and build some 2-3 horsemen. Don't bother about infantry. Once you have 5-6 units declare a war to your nearest neighbour. Try to get other civs as your allies in this war for now. Do not attack! Select a good defendable spot of land (might be a river valley or similar), preferably inside your borders for a friendly lands fighting bonus and faster healing and get them to come. Don't lose any of your units, if necessary retreat to heal. AI should send several waves of units and run out of them at some point. By that time you should have discovered mathematics and built a catapult or two. Now heal your army and go and get those AI cities. Raze them and leave a capital as a puppet (annex it then you have some spare happiness). Settle the land with your own settlers. Now do the same to the next neighbour...
- Developing. Constantly develop your cities, prioritize them. That means that some of your cities would be appointed to making money (if they have a lot of luxury resources nearby), some to making science (if they got jungle tiles), some to production (a lot of hills) to build wonders and units, some to make culture (none of the above advantages). You still need culture to adopt those all important policies even if you are not going for cultural victory. Dedicating city to some task means that you build that aspect enhancing building as soon as you have it available (markets, banks, stock exchanges for money cities, etc.) and you appoint specialists only to that same task. Still every city should have at least a monument, library, market and a coliseum. Make city-state allies. Preference is for not hostile ones with a luxury resource you don't have. After you make allies with several maritime CS's you can stop building farms and better build trade posts. Then make allies with cultural CS's. Forget about militaristic ones, unless they have a resource you so badly need.
Now if you still haven't lost your army at this point you should be doing rather well and can continue playing the way you like. Or if you want to be really effective and crush them all you can apply an ICS (infinite city sprawl) strategy. This strategy is genuine and it works perfectly, but honestly I don't like it myself at all, as it takes all the fun off the game. So if you enjoy Civ5 so far and want it to continue better close this post now, but if you want to further ruin your game experience read on..
The basics of ICS are explained elsewhere much better than I would be able to, so I'll just quote. Here's the theory behind Infinite City Sprawl, as written by alpaca in his Infinite Rome thread on Civfanatics:
The idea of an ICS strategy is to
settle cities as close as possible to
leverage the additional growth,
production and commerce that small
cities have over large ones. In Civ5,
there are a number of game mechanics
that lend themselves well to this kind
of strategy. To wit:
1) Maritime city states. The bonus
granted from maritime city states is
per city. Each adds +2 food to the
city tile at the start, increasing to
+4 over the course of the game. Since every city benefits from this free
food, a single maritime CS ally will
allow you to set up two additional
specialists in every in the later
stages of the game. Obviously, the
more cities the better, because each
gets the bonus.
2) Happiness buildings. In Civ5,
happiness is global... or is it? In
fact, only the consumption of
happiness is really global. The
production is local. Each city can
build happiness buildings, and the
low-tier buildings are more efficient
and more effective than the higher
ones. If you have lots of small
cities, each can have a Colosseum and
a Circus where available, and some
theatres. This actually rules out
happiness as a long-term limiting
factor and turns it into a
growth-limiting factor because you
need to set up these buildings in each
new city.
3) Purchasing things with gold.
Provided you have enough gold, you can
buy buildings where and when you need
them. Spamming trade posts is a
typical strategy, and it's possibly
even better in ICS. Just spam trade
posts, make money, and buy the
buildings you need. This is especially
good for the more expensive buildings
which have a better gold/hammer ratio.
4) Certain policies, like Communism
and much of the Liberty tree, scale
with the number of cities. So do some
civilization abilities or buildings,
like the one of Harun al-Rashid or the
Chinese Paper Maker. For them, you
also want as many cities as possible.
5) Research favors large empires
because a tech will cost the same, no
matter how many cities you have. Since
having more cities usually means
having more science, you will tech
faster.
6) Trade route maintenance makes you
want to put your cities as close
together as possible. City tiles are
free roads, after all.
There is a significant drawback to ICS
which I won't hide from you: The speed
of unlocking social policies. This is
the only thing that is really better
for small empires because, roughly,
your average culture per city is what
determines policy speed. Since there
are sources of culture that don't
scale with the number of cities, like
wonders and cultural CS, you will be
slower at unlocking these SPs, so make
sure you only pick those which are
most useful to you.
You can find some great comprehensive examples of how it is applied here:
http://www.garath.net/Sullla/Civ5/liberteordre.html
or here:
http://forums.civfanatics.com/showthread.php?t=390302
and this one is very short and straight to the point:
http://forums.civfanatics.com/showthread.php?t=388793
Expenses
The top two things that cost you money in Civ 5 are:
To reduce the first one, be strategic about what you build where. Cities should be focused on a task. Pick terrain, tile improvements, and buildings that compliment this focus. For instance, if you are building a production-focused city, build it near hills and forests, and focus on military and production enhancing buildings. Don't build science or cashflow generating buildings, since you won't be producing much of those in this city.
Likewise, if you are building a science focused city, don't build military or other production enhancing buildings there. The city's focus should be on science or economic enhancing buildings instead.
The only exception is happiness - in order to maintain a positive balance on the happiness scale, you'll likely have to build some happiness generation buildings in most or all of your cities. This tends to be one of the largest trade offs economically in most of my games - do I make the people happier, or do I bank some extra gold?
You can also guide each city's governor to focus on a particular area, and this can help your citizens understand what they need to do in order to support your vision for the city. If you leave the governor alone, the city may ignore some of your tile improvements in order to work tiles that create something you're not interested in, but which makes the city's output more balanced.
Also, don't let your workers run free - focus your tile improvements on whatever works best for the city the tile is in the radius of. Automated workers don't always pick the best terrain improvement for you. They may destroy forest or plant farms around a city that is going to be production focused, for instance.
Every unit you produce costs you money every turn as well. Try to focus your attention towards a small, but mobile army, and don't fight on multiple fronts if you can avoid it. Mixed unit tactics involving ranged artillery units and close-up front line fighters work best. The AI is terrible at war, and they will generally start on the offensive, even though you've likely got your army massed and ready to funnel them into a meat grinder.
If you find yourself with a strong surplus of units, gift some to an allied city-state. You'll gain influence with them, and if you declare war, those units are likely to still benefit you indirectly.
Income
You gain money via citizens assigned to money-generating tiles, trade agreements with other Civs, and by trade routes between cities. Any duplicate of a luxury resource does you no good - it is there to trade.
If you end up with 2 of a luxury, or more of a strategic resource than you need, find someone rich and sell it to them for a tidy profit. Suppling your possible enemies with strategic resources might sound like a bad idea, but since you control the flow of that resource, if they start doing something you don't like, you can cut them off and drastically reduce the effectiveness of any resource-requiring units they produced in the meantime.
There's also a glitch that I don't believe has been patched whereby if you destroy a luxury good improvement (thereby reducing the amount of that luxury good available) you can end a trade agreement early at no penalty, and then rebuild the improvement and sell the good back to that same Civ for another sum of money. This could be considered cheating, and I imagine someday it (will be/has been) patched however.
Roads between cities are generally profitable, but you want to try to minimize the number of redundant road links you have, as having 2 roads between 2 cities counts the same as having one, and costs you extra.
Best Answer
Declaring war might just be enough. If you can do damage to their military while they're on the offensive (via defensive unit placement on your side and strategic coastal city harassment on theirs), you'll probably end up with a net decrease in their overall science/space production. The CPU will also prioritize building replacement units, even though you are both very far apart. If you set up adequate defenses on your end, even if they come knocking their military won't be able to make much progress.
If you can get a few other nations to join in your fight, they might make the war a little more "real" and bear the brunt of the harassment. You can also use allied city states or Civs as a staging ground, as you suggest. However, you'll have to be careful that your allies don't lose, thereby causing Russia to grow ever more powerful.
I wouldn't bother trying to take territory from them unless you can really cripple their military first - and they'll probably be begging for mercy by that point. As you've noted, trying to land enough units to make progress is going to be painful.
I'm not much for nukes personally, and it's possible that if there are multiple Civs in play that they will ally against you if you commit multiple nuclear atrocities, which could end up giving Russia time to rebuild while you fight a multi-headed war. Desperate times, though...