wherever you go, you will enjoy, australia is a wonderful and beautiful country with great people.
i would suggest either perth, i've not been, but friends rave abt. it. you can hire a car and travel down the coast to margaret river area. depending where you leave from, plane travel can be long, i'm unsure how long from cns.

or tasmania, again long travel but if you were considering melb. anyway, i think it's only abt. one hour or shorter to hobart. (once travelled in a very small plane and it took over 3 hrs, scary). once again either car hire or bus trips out from hobart to the rest of state, lots of history and beaut spots in this state. only had the opportunity to hire a car for one day in hobart and we drove out to a lake, name forgotten, and stopped for lunch at the most delightful tiny place called something like possum inn on the dewart river. the outdoor environment was great and sitting by the pot belly stove inside having lunch was fun.

or south australia, lots of wine country outside capital of adelaide and once again lots of history.

or taking the train from adelaide to alice springs (may not be possible to book tho.)

whatever you do, you will enjoy. cheers, trish