I've been to Melbourne, Sydney, and Brisbane. My advice is this: Unless you've never seen a city in your life, you should hire a car, and go cruising around Australia, especially the coastal areas (south coast, east coast, and north-east coast).
Most Australian cities are like smaller versions of American cities. Melbourne is like San Francisco, Sydney is like New York, Brisbane is Miami, etc. But the countryside has some really cool places not found in the US or England - massive cliffs, huge rocks sitting in stormy seas. Especially the south coast which faces Antartica.