Some tips and ideas. Your mileage might vary and people's opinions definitely vary. Try different things you read and see what works for you!
----
What's working for me is to buy outright a factory on each of my first few worlds, start a second factory (unless it's a small world), start a shipyard (unless it's your homeworld), then a lab or two, then a market structure. Eventually I build 1entertainment structure, 1 farm, and 1 embassy. If I build multiples of structures it's usually going to be factories, labs, or econ structures. Happiness is starting on or colonizing a world with a +production bonus tile (or +research). It's most critical to get your industrial base going, your research hopping, and your economy going. Econ is less critical immediately but it'll bite you later if you don't get it rolling early. Production makes all your social and military building faster so it's most critical, and you need lots of research going because tech is critical in games like this.
Keep in mind that eventually you'll have the ability to build galactic wonders - those take tiles too. I generally don't plan for them immediately - instead I squeeze them in as tiles open up via terraforming techs.
Use that 5000bc you start with. Jump start your production by buying some factories. I usually buy a scout or two immediately too, which isn't as good of a purchase, but I still do it. I might buyout partially built colony ships too to more quickly expand. It's not that expensive to buy a factory outright and you benefit from it the whole game. Buying ships is more costly and doesn't have quite the long term benefit - although buying a colony ship to reach a good world earlier and beat an AI to it is certainly a worthy investment! The sooner you grab and start developing worlds the sooner they start to contribute to your research and econ.
You have to kind of balance things though because some planets aren't that big and terraforming techs will be required before you can build everything you want. Some worlds are very small and will only handle a tiny amount of buildings. So far I always build a starport on every world so they can pitch in with constructor building at the very least. Not to mention that every game is slightly different so you have to make adjustments on the fly. But these are the general principles I've been following and they've been working well (on normal and tough difficulty).
I also plan to specialize a few worlds (at the least). You will be able to build "mini wonders" that boost tech, econ, and production (the "manufacturing capital", etc) so I'll plan and build to specialize a planet for each of those accordingly. It's rare, but you might get a huge world that can have several of those, as the minors usually do with their PQ15 worlds. For example, if one of your early worlds is of decent size and has a +production bonus tile it's a good candiate for your future "manufacturing capital world" - so you might build an extra factory or two there and leave an open tile for when you can build the "manufacturing capital" mini wonder. This results in a planet that can crank out ships very nicely. Do similarly for the tech and econ mini wonders.
On new worlds I usually only throw down my first 2 factories and a starport (buying out the first factory). There's no blatant notification when a new starport comes on line so this is my self - alarm for them (not queueing up more structures after them).
I'm not sure that all out specialization is required but some element of specialization is handy. You should plan to have a couple of industrial worlds to do the bulk of your ship building and you need to be strong in both economy and research so when in doubt build extra research or econ. On smaller maps you have less options and you'll most likely be limited in how much you can do anything - making expansion even more critical.
Farming is a double edged sword. More people means more taxes but it also means more problems handling morale. You can research farm tech to increase your population caps. So, you don't need to build a ton of farms unless you want to build a lot of happy structures to handle the morale problems. I'm guessing it's rare that you'd want more than 1 farm (although with the patch change Brad mentioned regarding farms today you might now need more).
The big trick is that you'll probably see worlds of size 4-12 for the most part and you simply don't have enough room to develop tons of structures, so you need to organize and maximize what you do have.
Beyond that, spread out your research somewhat so you get upgrades to the core facilities (production, econ, research, entertainment, influence) so that all your building autoupgrade and gain strength. Focus your military research to one type of attack and one type of defense (prioritizing attack over defense) based on what you think the AIs are going to have (you can kinda guess based on their trade offers and espionage). For example, if most AIs are trying to trade you beam weapon techs then chances are the majority of them are using beam weapons - so research and build beam defesne (on ships and starbases). Do similary for your attack vs what they seem to use for defense.
I like to pursue propulsion tech first thing so I can design and build faster ships. Just boosting your colonizers, scouts, and constructors from 2pc/wk speed to 3pc/wk helps you expand that much quicker.
I'm fond of economy starbases. If you have planets near each other you can often build them in a location that lets them boost production for several planets at once. They also help your trade income. I build starports on every planet and all my planets are building constructors if they have nothing better to do.
The resources you can build starbases on are huge - grab them early and as much as possible. Easier said than done sometimes but at the very least grab ones that are near you and try to "steal" them from areas inside AI influence too.
Absolutely make sure the very first thing you do is press F3 (I think) to get to the screen where you set your taxes and production levels. Make sure you are operating at 100% industrial capacity, jack up your taxes (I usually try to maintain around 60% approval rate or higher but it varies over the game). It's critial to be at 100% capacity immediately or you'll fall behind quickly. Capacity determines how much of your global income is being pumped into your production and research. If it's at less than 100% you're making more profit to bankroll, which doesn't do a lot for you usually - you need all your productivity going into structures, ship building, and research - not savings.
You might adjust your allocations between miliatry, social, and research - but you might also hold off on this til you get a feel for how you like to start. On normal difficulty I would throttle the AIs going 30/30/40 with rare deviations - I rarely touched it. On tough I've done a lot more micro management to be competitive. For me this also varies with map size. I've only been playing up to medium and there simply isn't that much to colonize even with a sweet start. On larger maps where there's more of a "land rush" you might jack up military production drastically so you can pump out colonizers faster to gobble up worlds. It's an investment of sorts - sacrifice research and infrastruce to get worlds. Then you shift once the "land grab" is done and recover.
Efficiency in the early game has a lot of impact. It's worth redesigning ships to fit the job perfectly to maximize your resources. For example, if you're going to use constructors right near your planets, they don't need life support or fast drives - so build em with as few components as possible. On the other hand, if you need to grab resources that aren't right next to you you'll need a beefier and more appropriate fast and long range constructor. Design for both and build what you need. It's similar for colony ships. No need to have life support and lots of speed if you're just colonizing that PQ4 second planet in your starting system. But if you're trying to nab a juicy planet from under the AI's nose you might need extra life support to reach it and as many drives as you can pack in to get there faster.
Good luck!
