I have two suggestions.
First, the Big Island of Hawaii. It offers a variety of things to do from mountain biking to snorkeling/scuba diving to hiking to fine dining. Truly an excellent mix of potential adventures. It also offers a variety of shopping from high-end places to Costco, so quite the variety.
Second, the Florida Keys. Similar to Hawaii, there's a lot of variety. I would suggest a middle key such as Islamorada (Morada Bay restaurant is fantastic) for relaxation. Key West is great for a young couple, with lots of night life (have to go to Mallory Square for the daily sunset festival).
I know they're both US, and perhaps not as "exotic" as other places, but certainly either of them are fairly easy to get to, safe, and offer great variety. Unfortunately I'm traveling with my work computer so don't have access to our pictures from last year's vacation to Hawaii.
I may be a little biased because we honeymooned in Hawaii and have been there twice since, and have been to the Keys many times (probably 8 or 9).