Making a come back is the most rewarding galciv experience if you ask me. I greatly enjoy being the absolute underdog.

Recently, I had a game on a Huge galaxy, playing as the Yor, with 8 other majors and a few (intelligent) minors. It was one of those games that just proves "location, location, location" as I was stuck in a corner of the map with just 8 colonisable planets nearby (none of them above a class 11), while the galaxy had over 250 habitable planets in it (I had access to about 3% of the planets for my "colony rush"). The distance to the nearest planet that was not part of my tiny corner was too big to get there before other AI, especially as the nearest planet was Hammer, and both the Thalans and the Areans started very close to the edge of the main galaxy, effectively locking me out of the planet rush. From such awful beginnings, great victories can be crafted!

What you need to realise is that you do not need to be the stronger guy to win a war. What you definitely don't need is air superiority, and you sometimes don't even need very local air superiority. What you do need, is decent soldiering tech, very opportunistic behaviour and the willingness to set the other races against eachother. Remember that conflict is pretty much unavoidable if you're very weak: so make sure that whoever is fighting you, also has to fight (strong) opponents.

Invade planets that other AI have cleared of ships whenever you can. If you can build a ship that can take out a single enemy defender, you can use it to take weakly defended planets. Etc. etc. This is the kind of game where you have to be smarter than the AI, and as the AI is a poor invader, you actually do have a shot.

In the above mentioned game, there came a point where there were just three of us left: the Yor (me, I now had about 6-10% of the planets), the Altarians (who owned about 25%) and the Krynn, who owned everything else. Everyone was at war with eachother, and my space was crawling with krynn and Alterians blowing eachother to pieces. I very much felt like I couldn't come out on top anymore, but in the end I did come out victorious, conquering both the Alterians and Krynn in an epic game that lasted over 14 game years.

If you are not too devastatingly far behind, you can use the AI's endless hatred for starbases to your advantage - place heavily fortified starbases (of whatever type you like) on the chosen AI's route to your planets and they will usually at least thin the incoming fleets. If they survive, and you can keep a supply chain of constructors to them, it can buy you enough time to either tech past your enemy or do a local space superiority conquest.

Fast ships and good sensors are vital when facing a superior foe - sometimes you can kite enemy ships for months at a time without fighting until reinforcements arrive.

In a situation where you've been immensely outcolonized, but aren't yet at war with the superpower, it is usually fairly cheap to get them to declare war on just about everyone else (or just the altarians if you're thrifty). Once you achieve this, wait a little while for their military to get out of position, then hit them as hard as you can. Priority is planets - especially their capitol or any minor race capitols they have taken. If you're lucky, close to when you're unable to extend versus their returning fleets is when they'll be amenable to a cease fire, and you can influence them from there (or build up and declare war again). If not, you're going to have to run and gun like HighWater describes (though I personally have not had success from such a deep deep hole as that Yor game).

The other option, if you realize you are blocked in, is to try and zerg rush the AI. Once you have semi adequate ships and planetary invasion just go full military production and try to pit all your economy against part of theirs. This is risky if you do not have an initial success or two, and can leave you further behind.

In general, though: foment discord, and fight sneaky.