Stay away from the nullabour (check a movie called wolf creek to see why), everybody in sydney is gay, melbourne's cold and wet (but was voted the worlds most liveable city 2 years in a row), adelaide is boring and full of churches, brisbane is full of tourists, but very sunny, don't even think about going to hobart, perth is beautiful but with a small country town mentality, darwin is dry, very very hot and very very dusty.
Enjoy.