Typically most of Hawaii works under PADI -
Professional Association of Diving Instructors | PADI so you'll have more shop choices if you go thru them. They have a dive store locator on their website so you can find someone near where you're planning to stay - there are good operations on all 4 major Hawaiian islands.
The certification you want is Open Water diver because that will allow you to dive independently with others. There are also resort courses or discover dives but they will require you to be accompanied by an instructor on every dive till you achieve Open Water.
An additional aspect is that PADI has online training so you can complete much of the classroom portion now allowing more vacation time for the actual dive certification process - which would then take about 2 mornings to do the pool training and 4 required skills dives prior to being certified. Many offer discounted dives after that also. All have rental equipment available generally, in May you're not going to need much other than mask/fins/boots/snorkel to complete the class - everything can be rented also - including wetsuits if needed. In May I dive in Maui in a t-shirt just to keep from getting sunburned.
If you don't have anywhere in mind yet, I would recommend Maui since for a new diver it's probably the easiest diving and among the best as well. Many of the shops teach a short class, do some pool work, some beach work and then depending on who you're using may do some shallow boat dives at the end of your course. You can probably fly there directly from SFO also.
One advantage Maui has is there is a lot of diving clustered in several areas. Molokini Crater off the Kihei area is shallower, protected good diving. The island of Lanai - accessed by dive operators in the Lahaina area is similar. There's also a lot of easy beach entries - a couple of which you'll utilize during your training. Maui diving is among the best of the 4 islands or possibly Kona but the best of that is more spread out. And most entries are off lava not sandy beaches - for new divers not used to carrying full scuba gear, it's sharp if you go down. Kauai being smaller just has less of everything. Kauai generally requires a stop in Honolulu first also. If it's of interest stay in the Poipu Beach area since all the dive operations are located there. And they teach at Koloa Landing, a shallow site nearby.
I haven't been diving on Oahu so will let someone else comment on that.
If you stay in the typical tourist areas on Maui - some shops I recommend. In the Ka'anapali, Kahana, Lahaina area either Lahaina Divers or Extended Horizons. Both offer PADI certification. So do others but they have the boats. Another option could be Tiny Bubbles Scuba - all they do is shore diving.
Scuba Dive Lanai, Molokini, Molokai, and Maui | Lahaina Divers
Maui Scuba Diving 808 667 0611 Scuba Dive Lanai Extended Horizons - Maui's Leading Green Dive Shop - Lahaina, Hawaii
Scuba Dive Maui Ka'anapali Lahaina Hawaii Snorkel | 808.870.0878 | Tiny Bubbles Scuba Diving Specializing in Private Scuba Dives and Scuba Diving Instruction on Maui
If you stay in "South" Maui, there's more options. B&B Scuba is one I recommend but there's at least 1/2 dozen other options. Google Maui dive operators for a complete list. Others reading this will likely suggest alternatives.
For more personalized instruction, look at Shaka Divers. There's also Maui Dreams Dive Co. in that area - all the the last do is guided shore diving/certification. They have space on Maui Diamond II - a dive boat that leaves from Ma'alea Harbor - a short drive north.
There's also more shore dive options in that area after you're certified, most of the shops can hook you up with other divers wanting to do that. MDDC has a buddy sign-up sheet in-store. Shore diving really cuts down on the costs.
Molokini Boat Charters, Scuba Classes, Rent Scuba Gear - Maui
http://shakadivers.com/
http://mauidreamsdiveco.com/
There are many other good Maui dive operators - the ones I listed I have some personal experience/knowledge of. Some of the larger resorts on Maui also have affiliated dive operators - either nearby or on-site. Most of those will direct you to their/shared dive boats elsewhere for boat-based diving since all the dive boats leave from one of 3 harbors.
Maui Dive Shops also offer certification. They are the only SSI affiliated shop on the island. So you would progress in your training through them instead. Worldwide PADI is a lot more prevalent at most dive destinations. MDS teaches PADI courses also. Boat diving with them requires a short drive to the Ma'alea harbor also so I just don't see any advantage.
PADI also appears to have some presence in your country also -
http://padi.dk/
Pick an operator based near where you plan to stay. And contact them directly with questions about class sizes, scheduling, requirements etc. If you do the e-learning here first ask about that also - at one time you needed a referral code at sign up.
Although it doesn't look far, the drive time between Lahaina and Kihei can exceed 45 minutes with traffic. And the boats leave very early from Kihei to get to Molokini before the tradewinds pick up most afternoons.