In Ayers Rock, everything is overpriced by roughly a factor of three compared to the value anywhere else in Oz. That's because there is a single monopoly operator called Voyages. Closest you will get to luxury is Sails in the Desert, which has a minimum two night stay requirement. Some folks really like it.

Cairns, no luxury hotels when I was there, I think the two best are the Hilton and the Sofitel (the latter adjacent to the casino). If you want luxury, drive a bit further north to Port Douglas.

Sydney: Park Hyatt, 4S, Observatory maybe?