Another alternative is a program called Discover SCUBA. Many of the PADI shops in Hawaii offer the program. You get a few hours with an instructor, then do a 2-tank dive the next day. Depths limited to 40', 4 students per instructor. It's more expensive than a regular 2-tank dive, but an easy way to get in the water.