Я то же самое хотел написать, что и коллега: Лангкави Вам подходит. На этом острове есть аэропорт, куда за 20-40$ можно долететь из КЛ или Сингапура. А потом за 20 ринггитов на такси до отеля. Добираться, как видите, очень легко и просто. Только если Вы ищете такого уединения, что на всем пляже никого кроме вас не было бы, то такого на Лангкави не будет. Во всяком случае на пляже, который под аэропортом расположен и где сосредоточены все отели и весь массовый отдых. Для уединенного отдыха следует, полагаю, селиться в отелях на северном берегу. Но они там уже не по 15-25$, а значительно дороже.
Если желаете более уединенного и экзотического пребывания на пляже, то присмотритесь к острову Тиоман:
Тиоман. Сравнение пляжей. Видео, фото. Но туда не добраться из КЛ самолетом, а надо ехать автобусом, а потом на пароме. Но это того стоит.
Какую страну после Бангкока посетить - Сингапур или Малайзию - зависит от того, откуда будут до Москвы билеты дешевле - из КЛ или из Сингапура.