I'm flying into Melbourne, Australia first thing in the morning in a few weeks. At that time of the morning (rush hour, I assume) a taxi would be madness. What's the most cost efficient form of public transport from there to the city center?
The Melbourne airport website has a section on public transport, which basically means buses. They recommend using Skybus to get into the city centre. I've used Skybus before during rush hour going the other way, and found it fine. The price should be quite a bit less than a taxi too.
It sounds like you should be arriving at the right time to take advantage of the Skybus hotel transfer service, where they'll take you from the Southern Cross Station (where the coach terminates in the city centre) to your hotel / hostel, which should make your journey easier.