追加で海外も

沖縄の事ばかり書きましたが、国内には興味無いや～さんならと思い補足的に国外でのお勧めを2、3。

行き易くて無難なのはサイパン。まあ昨今は結構高いです。物価も高い。宿泊施設も(捜せば安い所は少ないけどあるはずですが)高めが多い。
海は中心を外せばそれなりに綺麗です。手ごろで行き易い割にイメージよりかは海は綺麗。ビーチはまあそれなりですが、ダイビングとかでボートでポイントまで行くような楽しみ方なら珊瑚とかの熱帯の海も楽しめるでしょうか。

東南アジアも行き易いのと、海以外も楽しい所多いのでお勧めですが、バンコクやクアラルンプールまでは便も多く楽勝ですが、交通の便の良い近場ビーチでは御世辞にも綺麗な海は皆無と思って良いです。(日本のビーチより下手すると汚い)
自分で手配する場合、綺麗な西や東海岸の島までは慣れてないと少し大変かもしれません。特にタイがクーデターですし・・・タイ南部は危険ですので、プルフンティアンとかに行くにはクアラからが妥当ですが・・・遠いです。
あと、他の方が書かれてるよう、地域と時期により半島の西海岸か東海岸かで雨期乾季の影響や海流、風の影響で雨がふり濁ります。特にタイ西海岸(スリン、シミラン等)は注意。10月末まではオフシーズンです。出きれば11月も止めとく方が無難。オフシーズンにはホテルとかも閉めるとこがあります。
逆にマレーシア東海岸は正月前後はオフシーズンです。11月頃～天候不順というか風があり船で渡れないケースが増えます。(ちょうどこの頃は西海岸はOKなのでうまく使い分けるほうが良いです)
シミラン等ならバンコクでなくプーケットへ飛べば比較的近いしクーデターの混乱とかも避けれるのではないかな?と思ったりします。クーデターやタイ南部については他にトピがあると思うので参照ください。

あとは、インドネシアですかね。バリ島の北部やロンボク、コモド等の島も奇麗とは思います。ただ、どちらかというとダイビング主体ですね。季節的影響は受けにくいので時期は比較的いつでもOKです。できれば11月～3月頃は雨期なので外した方が無難ではあります。もっと人のいない所へ行きたければカナワ、スラヤ島という小さな島がありますが・・・交通の便が悪いのと宿泊出きるところが限られるのでどうでしょうか?バリ本島からはダイビングのツアーとかでないと出ていないと思います。1度フローレス島に渡り(ここも奇麗ですが)そこから小さな渡し舟(といったほうがぴったりのやつ)で渡ります。
シュノーケーリングとか主体ならこの海域では最もお勧めではあります。ビーチエントリーも楽でGood。

オーストラリアも良いですが、ダイビングかもしくは都市部や内陸部観光か目的をはっきりさせないと航空券高いだけで終わりかねません。海関係ではリッチにビーチ遊びかダイビング主体でグレートバリアリーフに潜るならお勧め。それ以外はあえて勧めません。

フィジーは航空券高いのであえて勧めません。海はそれなりに奇麗。他の所より珊瑚とかのランクは落ちる気がしますがワイルドではあります。
海以外の地元の人が非常に良い感じなのでそう言う方面で癒されたい方には御勧めです。

ちなみに、沖縄以外で私的ランクを付けると。

1プルフンティアン
2スリン
3コモド、カナワ、スラヤ、シミラン

海の奇麗さ(主にビーチ主体で)がメインですが、ビーチで遊ぶ(シュノーケーリング程度)のしやすさ、宿等滞在のしやすさなども考慮しました。ただし時期はBESTのオンシーズンが前提。

でも、やはり・・・沖縄でしょうな^^。今から車で誰もいない秘密ビーチへ行く予定。那覇から1.5時間。教えないw。