I was last in Bali in November, I try and avoid the place and often transit via Singapore in preference. I am in Jakarta 2 or 3 times each year.
From Singapore to many ports can be had on the day for $30. I have had $5 flights (plus taxes).
From Darwin the hotspot at present is Vietnam, flights are a fraction the Bali price and the country is easier to travel about, the Dollar goes much further and the beaches are just as good as anywhere. Check out Jetstar or Air Asia prices from Darwin, Perth etc.
I never pre-book hotels.. they are chasing my custom, - I choose when I get wherever, and on the day.
Same with airfares, on the day travel is fine. Buses within Vietnam are about $6 per day and are Air Cond coaches.(Orange and Green buses),. Hotels are about $15 per night on average. A meal, with beers, $5.
Nha Trang would be the Vietnamese equivalent of Bali, it is nowhere as tacky, yet... Hotels are easy to find and cheap, I had a $8 room recently. There are quieter beaches, in fact the beach runs half the length of the country.
Forget Bali unless you like spending hour upon hour with a crowd acting like their UK soccer team just won their first game of the season. Culture... NOT.
I like Indonesia, I don't travel to see a bunch of foul mouthed drunken louts...
just me..