There are some world-class beaches on the Big Island. Really.
I’ve been to Maui 3 times, and we’ve always stayed in Wailea at the Renaissance. The hotel is small and quiet, and I think United has packages with them. There is a great footbath that runs along the ocean and all the other WAY fancier hotels so you can see how the other half lives. 
Wailea is nice and quiet and you can drive up to Lahaina if you’re looking for a crazy night out. You can also do a helicopter tour over Haleakala National Park, which gives you a breathtaking view of the volcano as well as waterfalls and greenery.
Sorry to say but the Wailea Renaissance will be torn down soon to make way for Starwood (St. Regis?) condos. 
Wailea is beautiful and great for honeymooners. There’s tons to do. If you go in early June you may avoid some of the summer crowd because school hasn’t let out yet in most of the U.S.
Things to do: hike, snorkel, scuba, snuba, sailing. I also highly recommend calling the Hyatt and taking a cruise on the Kiele V catamaran. They have a great lunch so come hungry. Wear your bathing suit and sit out front. Great view and guaranteed to get you wet.
Not much to do in terms of night life (well, other than the obvious for honeymooners) but I highly recommend Warren and Annabelle’s magic show, and I’m not into magicians. It was a great night out. Make reservations at Nimo’s afterward and you’ll be all set.
Yeah, our last trip there was November of 2004 and the staff there had heard rumors that they were being sold. What a shame to tear down such a lovely hotel! (Maybe e-logic can get a deal there before the tear-down date!)
On a whim, I checked out the reservations at Mariott.com. It looks like they’re taking reservations through August with nothing available after that. I bet the hotel is done for on August 31st. (my son’s birthday, how sad :()
You can’t really go wrong, but I would recommend Kauai for honeymoon purposes. There is plenty to do there, but it is much less hecitc, quieter, etc. and it is absoolutely gorgeous.