My two cents

It depends on which Alliance you want to earn miles on, what you wish to spend and whether you are using miles.

A. SkyTeam via ICN, GUM; Star Alliance via SIN, BKK, NRT; One World via HKG, SYD

B. Best fares will be via the Pacific onboard UA, JL and CO. The CO flight will be via GUM and only operates twice weekly; but, always see good deals. The JL flights also have good deals; but, low mileage acrual.

C. If you don't care what you spend - SQ - end of discussion

D. If you are redeeming miles. Star Alliance and book either the SQ nonstop to SIN from EWR or if not available for via Europe which will be faster to Bali.

If you get as far as SIN on a good fare, you have a great option in Valuair (Jet Star Asia) to get from SIN to DPS. Great service, very comfortable and very reasonably priced (by far the best price).

Enjoy and PM if you need any fuirther suggestions.