In my day, there was a little airline at Honolulu called Royal Hawaiian Air Service which operated a fleet of Cessna 401s. I did one trip from Honolulu to Kalaupapa on Molokai and from there we went low level (just out to sea) along the north coast heading east. The scenery is stunning and some of the waterfalls are spectacular. We landed on an airstrip in the middle of a cane field at Kaanapali Beach on Maui. (I think they have a proper airfield now). Anyway, if you can find someone to take you along that coast it is well worth doing.