Batam and Bintan are pretty crappy if you want a beach that doesn't have tar, effluent and/or sandflies all over it. Tioman and Redang are great, but the daily Berjaya flight is at midday, meaning that you effectively lose a day going there and coming back. So I'll join the choir and recommend Langkawi and Phuket... or Penang, if you haven't been there before; the beaches aren't as good as Langkawi, but there's a lot more in the way of culture and great food.