Uluru is a once in a lifetime experience but quite expensive compared to your other destinations (day there costs more than a week in Bali ). Its also kind of the opposite of Sydney that you mentioned loving.