Here is what I do...

I usually go straight to my homeworld. Start building a shipyard, and a couple of probes first thing. Then I decide what I want to be when I grow up... Researcher, Warlord, Trader... Then I pick a few skills to queue. If you only select one skill when the skill finishes training it will start training the next rank.

By then I usually have my probes popping out. After my 3 probes pop out I build a few mini harvs and start them on routes to my planets that are in my home system. Then while I wait for the harvs to build I start exploring with the probes.

It never gets old... I love seeing new solar systems when I find them. I make a note of what they have, and if it's a terran planet I try to make sure I get to it first to claim it with my colony ship. If I am a trader I will also note gas planets, since they will provide me with the rare ore I seek.

I will also note if I encounter other players in the early stages, because chances are it'll be their home world. I also avoid making enemies in my starting sector. Making allies out of the starting sector folk will probably help you all live MUCH longer.

That's my early game.