Welcome to the forum!

The below comments are just my perspective; other people may rightly differ with me.

I would recommend one of the Dutch islands: Aruba, Curacao, Bonaire or St. Maarten. Aruba is hot, windy, somewhat commercialized, generally inexpensive to get to and OK priced once there. Curacao is less commercial and has a nice European feel to it, but it is not as easy to get to and tends to be pricey. Bonaire I have been to once, never overnight; it, like neighboring Curacao, is not easily gotten to and seemed expensive for the brief time I was there. St. Maarten is somewhat rundown but still nice; I like the French side of the island best, particularly the beaches. French beaches are always the best beaches. Speaking of which, you can try Martinique or Guadalupe, but good resorts there may be out of your price range. Indeed, your $600-$700 per person budget may be a little tight for anywhere in the Caribbean, considering all the activities (sailing, jet skiing, etc.) you want to do, not to mention the extra dollars that AI is going to cost you. And May is not really bargain season yet, though some bargains can be had.

If you don't have passports, you may want to go to the U.S. Virgin Islands, St. Thomas (easiest) or St. John (lush).

Good luck! And be sure to give us a trip report when you return. ^