Well, request was for 'couple nights on a really gorgeous beach'. I do not think neither Bintan (where trash is just 100m away after 'official' beach ends) nor Langkawi qualifies.
As it was said - LCC and 1.5-2h flight from Singapore will take care of it.