I'll have to chime in with a recommendation of the Big Island as well (I've been to both Maui and the Big Island). The diversity of scenery is amazing! We like the beach areas around Waikoloa.

larry