I'm planning to visit some of the same places at the same time you are and so have been doing a little research. The Westin Sydney seems to come up time and time again as one of the best hotels in the Starwood Group. Rates are running about 290 AUD. People seem to like their hotels in Melbourne too - you might do a search on the Starwood forum on the FT Miles board and check out the comments.

You might want to check out this website for the time you plan to spend up north. Some of the whole house rentals look fabulous and for so little money. I think we're going to divide our time between one of these houses in Port Douglas and a sailboat charter in the Whitsundays.
http://www.portdouglasaccom.com.au/

Have fun.