Min erfarenhet av Bali är att de södra delarna är bäst. Var där i våras och åkte runt hela ön. Norra Bali kan ni skippa helt (enl. mig), det finns inget vettigt att se där uppe! Samma sak med Candidasa och Sanur på östkusten, bara ett paradis ifall du är Australiensisk pensionär.
De platser som jag tyckte bäst om var halvön söder om Kuta, med Bingin, Padang padang och Anjungan beach. På Bingin är det smockfullt av ganska billigt boende precis nere vid vattnet, och de har ett break där som jag surfade på (och jag är också nybörjare). Uluwatu är en välkänd surfspot (tydligen) och det ligger också på den halvön.
Åk runt lite på där nere så kommer ni hitta bra boende och bra stränder!
Höjer ett varningens finger för Thomas Homestay vid Pangan Pangan, sonen där är en tjuvaktig liten horunge.
Även Medewi uppe i sydvästra Bali var ganska sjysst. Bodde för 27 kr/natt där. Surfing även för nybörjare en bit bort på stranden.
Har själv inte varit på någon annan ö i Indonesien, men vad jag hörde av mina medresenärer var att Java var lite för trångt, och att man istället borde åka till västra Sumatra.