There’s a saying (said mostly by Melbournians) that goes “Melbourne’s a lady and Sydney’s a whore.”
Melbourne is Australia’s cultural centre – think good food/wine/beer, art galleries and museums, performances, live music, sport, street art, as well as being very easy to get around on public transport or foot. It’s sometimes called Australia’s most European city but you’ll need to be patient and take time to get to know her. I’ll happily admit it’s not the sort of thing international tourists come to Australia for, Melbourne’s made for living in, not visiting.
Sydney is flashy - beautiful harbour, land marks and beaches that will blow you away the moment you lay eyes on her. More than a few days ‘fling’, however, and it’s easy to get weary of. If you do make it there, do the Bridge Climb.
Queensland (north east portion of the country) is like a theme park. Great Barrier Reef, tropical rain forest, theme parks, outback desert, lots of glitzy tourist oriented destinations. I don’t like it but I can see why an international tourist looking for the stereotype ‘Australia’ would want to visit. As a diver, I’d say the GBR isn’t as good as you’d think. The reason it’s famous is because it’s big, but there are a lot more beautiful reefs in the world.
If you are after real outback wilderness, then Darwin is your pick. If you have time, then overland Darwin to Adelaide is apparently like another world. It will be stupidly hot that time of year though… expect 45c in the centre of the country with little shade to be had.
One thing to keep in mind – Australia is big!!! Land mass wise it’s as big as Europe without the Russian part, or as big as continental United States. So if you want to see a few different places, plan to fly. Even then it’s a 5hr flight time between Sydney and Perth, and if you wanted to go to/from somewhere more regional you’d probably need a connecting flight.