First off, split your starting fleet into individual ships and have them explore your immediate region while your science ships survey habitable systems and those within your borders. I always build a second science ship as well. This second ship should have a leader with a research related speciality. As long as you're not playing a fleeting species you should be able to swap him into a research spot when he reaches level 4/5.
Your first goal should be to build your military up to 10 or so ships, then get your colony ship out. After that, get your fleet up to the cap and go to war. Aim to destroy the economy and fleet of the enemy then sue for peace. You just want to cripple them, and if possible, take a colony that has no spaceport yet.
That's my standard start and it works pretty well.