Let me tell you a bit about diving the Hawaiian Islands. Hawaii diving is slightly more strenuous than other places in the world. Destinations such as the Carribean, the Red Sea, or Malaysia usually have fairly calm waters much of the time - ie. no swells in most spots, usually clear, and not very deep for most sport diving sites. The Hawaiian Islands are little specks in the middle of the huge Pacific. The water can be placid at times, but can turn tumultuous in the blink of an eye. Remember, Hawaii is known for her awesome swells and currents, which is why Hawaii is considered one of the world's leading surfing destinations. Also, the Hawaiian archipelago is a moutain chain that decends for miles beneath the surface of the ocean. A three minute boat ride can take you to waters that are miles deep! So, sites are not as spread out as in places like the Carribean. This means that you have to know where to go.
In order to fully understand Hawaii's ecology, one must consider that the Hawaiian Islands are the most remote archipelago in the world - i.e. they are further from any land mass than any other island group. For this reason, over millions of years, there have been only a hearty few species of animals to "naturally" colonize these islands. Larval fish and invertebrates and algal spores that chanced upon Hawaii, speciated (evolved into new species) and flourished. It takes a long time to drift to Hawaii from other parts of the Pacific. This is why species diversity is generally low in Hawaii (the term for this ecological condition is depauperate). If you were to compare marine species numbers in Hawaii to other places in the world, you'd soon realize that Hawaii has only a fraction of the species of other places in the Indo-Pacific. Hawaii has a mere 480 described species of fish. However, the romoteness of Hawaii does have other notable advantages regarding the variety of fish. For example, Hawaii has the highest rate of endemicism in the world - meaning, there are more unique species of fish, invertebrates, and plants in Hawaii than anywhere else. One third of Hawaii's fish, one fifth of the invertebrates, and one fourth of the marine plant life are endemic to Hawaii - found ONLY in Hawaii. THIS is what draws divers to Hawaii. It is an opportunity to see things that are found no where else in the world. Hawaii does not have the coral abundance that one might find in the Indo-Pacific or the Carribean since corals in general do not have long-lived larval stages that would survive the long trek across the giant Pacific desert. There are only about 48 distinguishable species of corals in Hawaii (I use the word "distinguishable" because recent work in coral genetics suggests that there are many undescribed species of corals in Hawaii that are phenotypically indistinguishable - that is, they look the same on the outside, but are genetically different). The depauperate nature of Hawaii's undersea world probably won't be apparent to most vacationing divers. There is still plenty to look at. What Hawaii lacks in diversity, she more than makes up for in sheer abundance!
Now to the "WHERE" question. Let me first start with the Big Island and Maui (since I know the least about them).
The Big Island (HAWAII) is where you will find the calmest water on average - (the water can be calm throughout all the islands, but The Big Island is calm more days out of the year than the other places). I would recommend looking up Jack's Dive Locker or Kona Coast Divers. They will show you the hugest expanse of Porites corals that I have ever seen in my life. The manta dives on the Kona coast are supposedly incredible.
On MAUI, I would look up Ed Robinson's Diving Adventures OR Extended Horizons. They run two of the premiere dive operations on the island. Ed Robinson is one of the top underwater photographers in Hawaii. There are other dive operators on Maui, but I don't know much about them. If you do dive with another company, please give me an impression of your trip. There are a few good spots on Maui to dive, though one of the top dive destinations in Hawaii is Molokini Crater. Some operators will also take divers to Lanai.
The next island is O'AHU. This is most likely where your plane will land first if you are coming from the mainland. O'ahu is the most visited of all the Hawaiian Islands. The capital city, Honolulu, is found here as well as Pearl Harbor, Waikiki, and Pipeline. Any local shop will tell you where all the best dive spots are, but I really enjoy the sites on the north shore, but only in the summer since the winter months bring 40 foot swells!!! Of course, diving the island by boat is preferable. One of the top dive destinations on the island is Moku Manu. Despite repeated attempts, I still have not been out to this dive site, but have heard that it is incredible. Some operators to check out: By far, the most successful dive shop on the island is Aaron's Dive Shop in Kailua (on the southeast side). They can also set you up with dive boats. The employees are helpful and knowledgeable. Please let them know that Kimo from UCLA sent you.
Now to KAUAI, my home island. There are a number of dive boat operators on the island and I have either worked or have been in close contact with most of them. If you would like information on these operations, feel free to e-mail me, but in my experience, the best dive charter on Kauai (and quite possibly the entire state) is Bubbles Below Inc. Scuba Charters. Bubbles Below is owned and operated by Linda Marsh (formerly Linda Bail), one of the most knowledgeable and experienced scuba professional in Hawaii's dive industry. Linda does NOT have a dive shop - she does boat dives exclusively; the idea being, she doesn't deal with retail - she just takes people diving. Her scuba tours are geared towards marine ecology enthusiasts and I guarantee that you will leave her boat more knowledgable about Hawaii's marine ecosystem than you ever thought possible. Bubbles Below has been running charters on Kauai since 1984 and operates one of the sturdiest dive boats on the island (their boat was actually designed to be a dive boat). The Bubbles crew has built a reputation for quality, and the majority of their business is repeat customers. If you are an advanced diver and are looking for an operator who won't bore you, you should dive with Bubbles. Linda has over 50 different dive sites around Kauai. She is a true marine enthusiasts that will keep you completely occupied while underwater. Bubbles Below is also unique in that they issue (free of charge) computers to everyone, so the whole group gets the maximum safe bottom time allowed. There are a few shops on the island that can help you with gear rental. Fathom Five Divers in Koloa Town, Kauai Sea Sports in Poipu, and Dive Kauai in Kapaa are all excellent shops, or you can now rent directly from Bubbles Below.
There are a few companies that have ventured to take visitors to the Forbidden Island of NI'IHAU, but if you want to go with experience, go with Bubbles Below. They have been running Ni'ihau tours for over 35 years and have masterfully constructed a first class experience for SERIOUS divers. As far as I am concerned, Ni'ihau is the best chartered diving in the state of Hawaii and possibly the entire Pacific. Ni'ihau underwater is like Texas - everything is bigger and there's more of it! Ni'ihau is great for seeing pelagic sharks, rays, the endangered monk seals, and rare turtles. However, I only recommend Ni'ihau diving to intermediate or advanced divers. There are some spots that are good for drift dives and others where divers must feel comfortable with ascents and descents without an anchor line. There are lots of ledges and walls that drop off into 300+ feet of water and divers must be able to control their buoyancy at all times. There are huge lava caves and lots of critters. If this is your type of diving, I highly suggest doing it. Because of the sea conditions from November through May, Ni'ihau trips are mostly run in the summer months. Every now and then, companies will run tours in the off months if water conditions permit - because the ocean is somewhat unpredictable in the winter, it is difficult to plan a Ni'ihau charter very far in advance during the non-summer months. This is a good thing to know if you are visiting at that time. So go ahead and inquire about Ni'ihau, but don't be discouraged if you don't get to go - there are lots of great things to see on Kauai too. If you'd like more info about Bubbles Below, visit the Bubbles Below Inc. Scuba Charters web site. They can also give you other info on conditions, other dive operators, and other travel plans - oh, and tell 'em KIMO sent you.