私の体験した範囲では・・・

・タヒチ
飛行時間が約10時間と遠いのと、費用が高いのが難点。
でも現地は素晴らしいです。安宿を利用すれば割安にあ
がるでしょうが、彼女同伴では雰囲気が出ないでしょう。

・ニューカレドニア
飛行時間は約9時間。タヒチよりは費用安目。イルデパン
など離島がおすすめ。

これらについては詳細レポートがありますので、参考まで
にご覧ください。

http://yasyas.web.infoseek.co.jp
(それぞれタヒチ編、カレドニア編をご覧ください)

また近場では、テニアン、ロタ島などもあります。
これらの体験はありませんが、近くて安上がりにい行ける
のでは?