Help me get off the ground

Unfortunately, the AI knows where all the good stuff is right off the bat without exploring, which I don't like.  They usually head right for it, so you do have to hussle at first to colonize.  Usually your economy WILL go down as you colonize, but should slowly go back up as the populations of the planets increase and you get tax money.  

I usually explore the stars in the direction of my closest neighbors first, because I assume they will send their colony ships there first as well.

Just lower the difficulty until you can more or less compete with the AI on a more equal footing. Once you can do that then it's time to increase the difficulty and learn how to do it all over again.

The bottom line is that you will eventually get to the point where it's humanly impossible to compete on an even level with the AI however you do need to make sure that you *can* at least compete with the AI up to the point that it *is* humanly possible to do so.

When you get to the highest levels then you'll be pretty much back into the position you describe above however at that point it will be because the AI is getting huge bonuses and not because you missed out on important development of your game as you were learning.

At that point the way to win is more by the indirect method. You might find that you do need to bribe an AI not to attack you or that you do need to research and build the Spin Control Center and put up a handful of paper tigers in orbit about it so that the AI's think you're strong and leave you alone for a bit. You can then use that respite to get stronger so that you have a chance against that first AI. Once the first is conquered then you have that much better chance against the 2nd and so on.

If you're familiar with the 4X style of game then it should be obvious that growth is exponential. The more resources you gain the faster you can gain even more resources. With the bonuses available to the AI at the highest difficulty levels there's simply no way to *directly* get onto the same growth curve that a Suicidal AI can maintain. But that doesn't mean that you can't compete, it just means you can't compete using the brute force and ignorance method of simply having a bigger stick than your next door neighbor, you need to use things like diplomacy to gain an advantage on them and work subtly at the margin playing one AI against another until you're strong enough for a direct attack.

Some people don't like this and prefer to play at the Tough level which is the point at which the AI and the human receive equal bonuses. The Tough level can in fact be very Tough and certainly starting out I recommend you start at a level below that, however if you plateau at the Tough level at least you have a reasonable chance at playing a straight up game with an even chance against the AI and if that's how you prefer to play then there's nothing wrong with that.

Uncommon habitable planets is making your life more difficult, as the importance of colonizing planets is bigger than when you're playing with common habitable planets. I would think loose clusters are also slightly tougher since it requires more flying around to find the habitable planets.

Some pointers that will hopefully help you. I'm not the most experienced player around, but I win most games on painful difficulty, have a tougher time doing the same on crippling - so this will work on Normal difficulty:

1) Don't colonize Mars: there are very few usable tiles on there. The influence from Earth once your population has grown to its full size, should be enough to culturally flip Mars back to your control - and the AI has paid for its development. The same goes for other low quality planets (e.g. quality 5 or less)

Instead, use your survey ship and 1-2 scouts to look for better planets (higher planet quality --> more usable tiles) nearby. Don't try to take the really distant ones either: the key is to get your first few planets up and running as soon as possible

2) You shouldn't need an economic starbase to keep your economy above -500bc. Instead, research technologies that give you an increase to economy or morale. At some point you'll need to go to lower approval ratings in order to avoid going into too much debt.
Regarding approval ratings: at the start, set your taxes so that you have 100% approval rating (your population growth receives a boost that way). It's tough to say when to increase taxes but I would say, if your current spending gives you around 40 more weeks before you go into debt, go to 76% approval on your capital planet and preferably still 100% on other planets. (76% approval also gives a boost to population growth, though less than at 100% approval)
If your income is still too negative, consider going for a lower approval on your capital planet (above 46% to keep some population growth) until you get access to good morale buildings such as a political capital

3) Which picks do you choose? In your first games, it's probably best to spend a maximum of points on economy.

4) Which political party do you choose? Here again, federalists will make it easier to keep your economy in the green. As soon as you research more advanced government types, your economy will improve.

5) Have your capital and 1-2 other planets focus on factories and building colony ships as soon as possible. Rush-buy 1 or 2 factories on each of those planets, it's worth spending 300-something credits to gain speed.

6) In addition to technologies that give you an early bonus to morale, research, military/social production, make sure you also research better engines or technologies that boost your speed. Especially in a large galaxy, your colony ships should be fast enough to grab those planets.

7) Research advanced computing and trade early on, then build a tech capital and econ capital.
Typically I put my econ capital on my capital planet, while I devote another planet entirely to research (2 factories to get construction going, then labs, followed as soon as possible by a tech capital)

8) Tech trading! The AIs trade a lot of technologies between them. Buy not-too-expensive technologies for influence points or some of your own technologies (preferably not the really good stuff and definitely nothing that gives them a diplomacy bonus). Also trade technologies with minors. You can pretty much sell them any technology except the ones with a diplomacy bonus, either for technologies or for cash.

9) Keep an eye on the military rating (display at the bottom of your screen, in the middle - the default view is population): as soon as the AIs start building any military, don't wait too long before starting your own. I would recommend going for a decent hull size (e.g. medium) and some miniaturization quite quickly, rather than going too much after more advanced weapons that take a lot of time to research. Once you have some military, consider researching yellow techs in the "majesty" branch to the end. The final technology allows you to build a spin control center which gives a huge boost to the military rating of the planet it's built on (multiplies the military rating of all the ships in that orbit by 10)

Let me know if this helps or if you need more specific tips & tricks...

This is good advice, I always pump points into 'economy' and choose Federalists as well...

Thanks for the advice guys.

For my picks, I run Bravery, Creativity, luck, +20% economy and +20% research.

I've been alternating Universalists and Industrialists. I don't like Industrialists. I tried Federalists, but didn't notice enough of a difference.

Changing the planets around has helped a lot, actually. Thank you.

I still find trade imperative to economic success, and economic starbases too useful for my money/production planets.

Getting better, though. I figured out one thing I was missing: Planet specialization. Old habits from Civ II die slow

Lastly. I'm confused about warships - what is a good point to focus research on them? How to use defenses effectively? And, what is a good point to say "Okay, this warship will do for a while" and go back to economy/industry/diplomacy research?

Creativity is nearly always a nice pick; not so sure about luck (as I'm not even sure what exactly this is doing). I wouldn't go for bravery unless you're planning on playing rather aggressively.

Don't get me wrong, trade is still important even in a large galaxy. Not just for the income but also to improve your relations with some AIs. However your priority should be grabbing galactic resources and colonizing planets. Only once that phase is over and you've further developed your galactic resources, it's time to build freighters and economic starbases (the benefit of having a few constructors develop a galactic resource is far bigger than having the same few constructors build an economic starbase)

You can have a planet focus on either military production, social production or research: open the screen with the planet details, then click at the top on any of the 3 symbols (hammer, beaker, ...); the symbol that is highlighted is the one that the planet's focus is on.

Also, don't forget to play around with the overall military / social production / research sliders, depending on your current priorities.

Regarding warships: I try to take the lead in hull size, or at the very least keep up with the AI. In addition I keep an eye on total military rating and on any enemy ships I see (whether they are flying around or just in orbit). If my own ships' attack is far lower than that of the AI ships, it's time to research better weapons. You can also get a view on where the AI is: whenever you're trading with them, take a look at the weapon technologies they've researched and compare that to your own to ensure you're not far behind.

If you're an evil civilization, research Xeno ethics and choose the evil path; that will unlock very potent weapons further down the tech tree!

Also keep a close eye on the defenses that the AI is adding to its ships, especially if the defense type corresponds to your attack type. The last thing you want, is to run into a fleet that you cannot attack effectively because your weapons are too weak to penetrate their defenses.
I can't give any decent recommendations on defense since I usually go for all-attack ships. Hopefully someone else can contribute... In any case, if you plan on using defenses, target which AI you will most likely be fighting and see which weapon type they're using, so choose your defenses type accordingly.

Going on what most have said..I Colonize worlds near my home world first..and when I can I build  the appropriate structure on the appropriate tile..I research building on research tile factory on factory tile..etc

but the key thing i found was to just build a star port and when available a recruitment centre..and then just the leave the planet alone for a few turns dont build anything else unless its a bonus tile (more structures = more maintenance cost)..the rec centre provides a 20% economy bonus and pop growth bonus..I soon find my economy pick up and back in the green.

Also keep up your trade early on as it will slow down the AI from giving you grief aswell as boosting your economy..but when you can afford get a military up and running soon..a few tiny/small hulls with early stage weapons/defences will keep the AI off your back..and trade heavily with minor races..its like having your own ATM.