You can get a trip with Waterways for a two week stay out of NYC for about $4500. That was a couple years ago, might be more now for fuel. You fly into Padang, then get a 40ft catamaran with about four/five other people, and live on the boat. Excellent, no bugs, air conditioned, first rate food. You can pay more for a bigger yacht, but then you might have 10 or more people, and that's like having your own portable crowd.
It's better on a smaller boat. The captain always tries to get you reefs alone if he's any good. Waterways does it all for you.
I went with four of my friends, so we had the boat all to ourselves.