What to do downunder

Below is a 'big picture' view with a bit of a flavour of the places and what you can see.

Cities

Brisbane - warm, friendly, attractive and fun; great for being outside, riding the river ferries, beautiful ocean beaches nearby (Gold Coast, Sunshine Coast, Stradbrooke Island).
Sydney - gorgeous city and harbour; best seen from harbour ferries; late night partying; nearby iconic ocean beaches (Manly, Bondi, Coogee); terrific shopping, museums and opera house.
Melbourne - very European; sophisticated and cultural; a gastronomic wonderland; magnificent botannic gardens; great live music scene; sports mecca and fashion centre.
Adelaide - almost English; surrounded by wine regions; good food and access point to Kangaroo Island.
Perth - beautiful city on wide Swann River (sailing mecca) and near ocean beaches (Cottislow, Scarborough); good night life; see nearby Freemantle for historical sea port; access point to wonderful South West of Western Australia (see below).
Hobart - historical and clean city on banks of the Derwent River with Mt Wellington as backdrop; great seafood, crafts market (Salamanca); nearby Port Arthur provides the sites and feel of the penal colony past; access point for the many natural wonders of Tasmania.
Darwin - the far tropical north; laid back; magnificent sunsets; access point to Arnhem Land and the Kimberley (see below).

Natural attractions

Great Barrier Reef - a wonder of the world and must see if you are into snorkeling or diving; easiest access is from far north Queensland (Cairns, Townsville), but can also be reached from departure points within five hours drive north of Brisbane (see Heron, Lady Elliott and Lady Musgrave Islands).
Blue Mountains - a few hours from Sydney; beautiful region with sweeping mountain vistas, coloured by the eucalypt forests.
Cradle Mountain and Tasmania wilderness - lush and unique fauna; pristine wilderness, craggy peaks; wonderful fishing; amazing empty beaches (with very cold water).
Ocean Coasts - lots to choose from:

Great Ocean Road southwest of Melbourne - picturesque, lots of nice little ocean front towns with cafes; forested mountains drop down to the sea.

Northern NSW, south of Brisbane - beautiful sandy beaches and rainforest covered hinterlands; Byron Bay and lots of other towns to stay in.

Southern NSW, south of Sydney - fantastic scenery and less travelled countryside.
Sunshine Coast, north of Brisbane - just a little over an hours drive north of Brisbane, fantastic sandy beaches and Noosa National Park. Can go as far as Hervey Bay - the best humpback whale watching area.

Uluru, Kata Tjuta National Park - also know as Ayers Rock, a symbol of Australia and important Aboriginal centre, access via bus or car from Alice Springs
Arnhem Land - the far north of the Northern Territory, pristine tropical beaches and forest; stronghold of Aboriginal culture.
The Kimberley - rock gorges and sandstone formations, pockets of rainforest, a vast pristine wilderness.
Carnarvon Gorge - outback rocky gorge with lush rainforest oasis; about 8-10 hours drive from Brisbane.

Unique places and regions

Coober Pedy - the desert and opal mining centre with many underground homes to escape the searing summer heat; about 850kms north of Adelaide; can access via train (the Ghan) from Adelaide
South West of Western Australia - Margaret River wine region; old growth forests, Great Southern Ocean sea port of Albany.

Tip number 1: unless you really like driving, don't travel between the major cities and towns by car because you will spend most of your time in a car.
Tip number 2: search the web for locations, accommodation, things to do and see - most of Australia is well covered on the web.