My partner and I stayed at the Sheraton on the Park and later at the Westin Sydney over New Years. Both are beautiful hotels, nice big rooms, no problem what so ever about sharing a king bed. (But this has been my experience at both those chains world wide.) The Sheraton is easy walking distance to bars on Oxford. The Westin is also walkable, but slightly farther. Both hotels have great gyms, with the Sheraton being a bit more "interesting".

Also stayed at the Sheraton Mirage in Port Douglas. Nice resort, but a bit dated. If you're going to Cairns for Diving, Port Douglas is your best bet. Check out Poseidon Diving.