I can relate with not wanting to drive on the opposite side of the road, my husband and I tried to cross the big island from Aulani to surf at one point my husband just pulled over till no one else was on the road and immediately gave the hire car back after one trip.
The transport around the cruise terminal at Circular Quay in Sydney is amazing, there is no need for a tour there really.
Definitely fly from Sydney to Cairns the drive is 27 hours without stopping, hence no tour would go to both Cairns and Sydney by road. Adding Uluru (Ayers Rock is on old name for it) would be too long and dangerous, while I have met people who have driven from Uluru to capital cities people generally fly there.
I would:
- Stay in somewhere like/near the Four Seasons Sydney. The Four seasons is a bit dated, but corner suites have amazing views of the harbour and its within walking distance of the cruise terminal and opera house.
- spend 4-5 days navigating Sydney from Circular Quay using public transport, no need for a tour. You can walk to the postcard spots, catch a ferry to Taronga Zoo, catch a bus to Bondi.
- The train leaves from there to the Airport, it is insanely easy, and fly to either the Whitsundays or Cairns.
- If Cairns for 5-6 days you could get an airport transfer for $200 to not drive. I would stay in the Sheraton Mirage Port Douglas, like the 4S it is a little dated but because it is beachfront. Book a swim up room. From there you can get a tour pick up to go to the Reef with someone like Quicksilver, they will get you from the resort. Also do a day tour of the Daintree and the Kuranda Express is cool.
- If Whitsundays, I would look at Hamilton Island, like Cairns you can do tours. The Whitsundays are beautiful islands.
- Then I would fly to Uluru for the last 2-3 days, there are direct flights from Cairns. I think from the Whitsundays you would need to come back to Brisbane, but that would be a short flight. At Uluru stay at Sails in the Desert.
- From there you could fly back to Sydney to go home.
Another place you haven't mentioned is around Darwin where Kakadu is which is beautiful, I expect there are tours there, but it would involve another flight and more time.