You might want to reach out to Catherine, who is often on the "Hawaii Ohana" board. I know she's taken some great trips out of Honolulu -- including Bali and Palau -- so she probably has some helpful ideas and tips. Also, I remember reading that she used a travel wholesaler to get a really low fare out of HNL.
Outside of Hawaii, my Asia-Pacific diving experiences have been Australia (Coral Sea/Osprey Reef liveaboard) and Indonesia (Komodo liveaboard). I particularly recommend the Komodo trip!! Check out the Mermaid liveaboard, it's relatively inexpensive -- and Bali can be very cheap, too, once you're there -- you get a lot for your money.
Happy planning!
