It would be ideal for me to travel when the weather is not blistering hot but warm enough to enjoy a beach here and there. I have to admit that I'm not very knowledgable about your country but want to learn and explore something new to me.
I'd like to snorkel along the Great Barrier Reef, see Sydney Harbour, see Ayers Rock, learn about the countries history and see the native landscapes including the beautiful waterfalls and wildlife, taste wines and what ever other wonderful things that get suggested.
Sounds like spring or autumn........September. October, November is Spring.....March, April, May is Autumn (though, in the hot bits, April is more reliable as spring).
The Barrier Reef is in the tropics, so is pretty accessible anytime.
Uluru (NOT Ayers Rock, which is the colonial name) is best seen when not too hot...so late spring, or Autumn is great.
My state, South Australia, is the main wine state ( I'd be happy to show you round)...we have the Barossa ( a dream in Autumn), the Clare Valley and the Southern Vales.
NSW and Victoria and WA also have great wine regions.
Sinney Harbour is great anytime.
History is great anywhere.....but you ought to look for Aboriginal input wherever you go. They are the oldest continuing culture in the world, and many places offer Aboriginal input.
Sydney is the site of first European Settlement, and parts of Old Sydney, like The Rocks are great.
Tasmania is full of natural beauty and convict history, as well as glorious temperate rainforest, and tundra (Australia's Antarctic folk train there).
The Blue Mountains are wonderful.
WA has glorious country up north......and you have to see more of the Centre than Uluru.