Welcome to the madhouse Daniel
Unfortunately, your 'intended use' isn't enough for us to start suggesting bikes. Hell, with that we can't even define a TYPE of bike, even your old mtb with slicks will do what you want ... though I fully understand your desire for something better for the road. Sorry you mtb types, but mtb bikes work on the streets but bikes designed for it do it better just as hybrids and touring bikes work on the dirt but an mtb does it better.
$600 isn't a lot to play with. As Bnej suggested,
Cell bikes (and maybe a few others) sell new bikes for that. There are hybrids and 'comfort' bikes in that range too - basically, these are bikes with more upright riding positions and they are actually quite capable machines if you aren't after speed.
I sense that you are probably thinking more towards the racer - drop bars and a good turn of speed.
Well, you do NOT have to buy a racing bike to get that - have a trawl of the Trek website for instance (heck, look at all of them - Christopher, the forum host, has a thousand links on this forum's home site
http://www.bicycles.net.au/ ).
Just as there is nothing wrong with wanting to buy a light, skinny wheeled, bare basics racing bike, there is nothing wrong with wanting something a bit more comfy to ride (such as with wider wheels or a less extreme riding position). My personal approach was to buy a touring bike and set it up for around town work. My son's approach was to buy a racing bike and carry a ton of school books in his back pack.
It's about now that 'OMGosh, what have I got myself into' is an appropriate response
First, you do NOT have to buy from a bike shop, but if you do, the shop will set the bike up for you, make sure it's working and offer some sort of warrantee (especially if new). Most will also give some discount on items bought at the time (and you'll wind up needing extra kit such as pumps, etc) - you will need a fair bit of kit and no a lot of it is cheap (not if you want it to keep working - pumps spring to mind here and you'll need two, one for home and an emergency one on the bike).
However, it is unusual to find second hand bikes in bike shops. Some shops stock a lot, most only offer new.
DO NOT buy off
ebay unless you know exactly what it is you are getting. DO NOT be sucked in by some of the amazingly cheap piles or articulated garbage that is sold by many
ebay shops - Odin brand springs to mind.
DO NOT buy any bike you can not sit on, fiddle with and take for a ride, be it from
ebay, a bike shop or the bloke with all those tattoos and big dog at the end of the street.
Second hand.
Ebay (but test ride first), classified adds, Trading post, shop windows, garage sales, etc. All the usual suspects.
Buying second hand gives you the chance of a bargain - the bike bought but not used much for any one of a number of reasons (poor choice being one). You can also pick up eighties racers for some amazing prices.
And that is the route I would suggest for you. Buy an eighties racer, in good nick, for a few hundred bucks. Spend the rest of budget kitting yourself properly. That racer will give you a good six months or more of road riding, allowing you to develop some fitness, some strength, some skills, but more importantly, allowing you to work out exactly what it is you want to do with this bike.
You may find that although the attraction of going for multi hour rides along the coast is alluring, 'she indoors' puts a time limit on your weekend riding. You may find that the whole family gets involved and (not knowing your circumstances), you find your weekend rides taken up by escorting the missus and two kids on their bikes ... at a pace more suited to a hybrid than a full on racing bike. You may find yourself commuting to work and taking the occasional blast on the weekends. You may find yourself joining the local racing club and planning your assault on the criterium season over summer.
Give a cheap(ish) but good quality eighties racer a real hiding for six months, and you'll be ready to spend some money on a new bike, but a bike which you will know from the outset will suit you perfectly.
Richard