We always stay in West Maui, but it wasn't until last year that we discovered Artie and Piper at Pacific Dive. They have had our business since. You will find they have the lowest prices and are very helpful with information on current conditions. They do guided shore dives (at a reasonable price) and will also help you book boat dives. As they don't don't do the boat dives, I think you can trust them on their boat suggestions.
In April, you should be avoiding the worst of the north swell. With luck you should be able to do most of the west Maui shore sites: Honolu Bay (awesome reserve), Airport Beach, Black Rock (arrive VERY early to get one of the very few beach access parking spots at the Sheraton), and Mala Ramp (We love this site, Pacific Dive does guided dives here, this may ba an option for your first time there.) These are are shallow, so you can get some serious time on your dives.
We've done both Lahaina Divers and Extended Herizons for the Cathedrals. The Cathedrals are considered by most as a "must do" and I tend to agree. The area does have amazing structure with great vis. We had a less than enjoyable time with Extended Herizons, but we may try them again as their DMs have changes and they get great reviews from people I trust. Lahaina Divers has big / comfortable boats with friendly crews,,, but,,,, with a full load the lower deck can seem very small when trying to gear up and enter. You are also eight to one with the DM, this means NINE people in the Cathedral at one time (hold on to your regulator!). (Oh yes, smaller tanks too.)
If you want to check more boxes, heading down to Kihei (we always use Mike Sevrens) is a great time. (Coming from the East Coast, getting up early for Kihei shouldn't be hard.) A plug for Mike Sevrens here: If you want a real educational / environmental minded approach to your dive experience - this is the boat. You also have a crew of four for twelve divers = awesome service and safty factor.