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...