Billy, I would like to throw in a suggestion for a specific cruise ship -- the Paul Gauguin, which cruises French Polynesia and surrounding areas (the Marquesas, the Tuamotus).
This would provide you with the best of all worlds. I agree with those who suggested Bora Bora -- and the ship spends at least one day (and sometimes two) there. But it will also take you to the other islands, including Tahiti, Moorea, and several other nearby islands (depending on itinerary), while offering far more than you can get at any one resort.
Why do I think this would be the perfect honeymoon?
1. French Polynesia has gotta be the most romantic place on earth -- it's truly paradise -- but it's EXPENSIVE...unless you visit it on the PG. The PG is astonishingly affordable, offering a degree of luxury that you can't find in any resort in French Polynesia without paying ten times the price.
2. The ship is a six-star luxury ship, in a six-star luxury line -- it's top-notch all the way, from the cabins to the food to the service to...well...everything. It's not like what you would commonly think of when you hear "cruise" -- there are no belly-flop or hairy-chest contests at the pool, no long lines at all-you-can-eat buffets. Unlike the mass-market cruise lines, it's truly all-inclusive -- and I mean ALL! That includes fine wines poured liberally at dinner, top-shelf cocktails, NO tipping, NO extra charges for specialty restaurants, NO extra charges for anything. It's a small ship -- only 330 passengers, unlike most mass-market ships, which usually house 2000+ passengers.
3. You can dive...while your new bride can do other things! The ship has it's own dive crew (who are fabulous), and offers amazing diving from zodiacs right off the back of the ship. If your wife doesn't mind giving you up for a couple of hours, you can go on any of the many dives they offer, while your wife can perhaps go on a land excursion that you might not be interested in. Maybe a visit to a black pearl farm (the most beautiful black pearls in the world come from French Polynesia), or some other shopping-related excursion...or perhaps a snorkeling trip, or a dolphin-viewing excursion. The point is, this cruise is the perfect vacation for a couple in which only one is a diver, as there is more than enough for the non-diving person to do, while the diver can do some of the best dives on the planet. (Twelve-food manta-rays anyone? How about 8-foot hammerheads?
)
4. If you enjoy fine dining, it doesn't get much finer than this. The food on the ship is truly gourmet...and I'm picky. I've been on a lot of cruises, from mass-market to luxury, and most food at sea ranges from barely acceptable to downright inedible. But on this ship I felt like I was in culinary heaven, at every meal. This is particularly important if you are considering Bora Bora or any other island in French Polynesia. The reality is that food in FP is generally, well, not that great -- and it's WAY rediculously expensive. If you tried to duplicate the PG dining experience on any of the islands, you would easily triple your vacation spending, and it still wouldn't be nearly as good. I don't think I ate a single decent meal on land while I was there.
I probably sound like a commercial for this cruise, but I promise I am getting nothing to promote it...just the sense of satisfaction I'll get if a friend of mine gets to enjoy what ranks among the greatest experiences of my life! PM me if you want more info.
I wasn't even invited to the wedding! 
