My buddy dove with Kona Diving last year. He has a full video rig, lights, arms etc. and mentioned no problems. IDK about gear storage as he probably took his most afternoons to shore dive. They're really friendly if you call. It's a smaller boat so they limit the divers. It's also a cat so more stable than some of it's size. WannadiveKona is another option, they have a six-pack. They were our second choice. [user]friscuba[/user] owns it.
Lodging nearby is not what you'd expect. Most of the dive boats leave out of Honokohau harbor just north of Kona town. It's pretty much a desolate area with a few nearby industrial buildings and the harbor. Maybe just a mile? north of "downtown" Kona.
There's an older resort in town - King Kamehameha and a few condo complexes - most with ocean views, not many are waterfront.
You really want to stay south of Kona - there's about a 3-4 mile stretch of condos and resorts all down the coast. Since Hawaii is volcanic in origin, many of those, while waterfront, are not beachfront - typically there's large, sharp lava rocks going right into the water. So if a beach is important, find a resort on one or a condo complex within walking distance of one. Many that are will feature it as an attraction. From that area it's a couple mile drive to the boat harbor thru town - there's also a second road that bypasses any of the congestion (it's not much) going north/south. Some of the dive shops are in that area - there's a little industrial plaza where two or three of them are located - including Kona Diving Co. After you check in with them once, you'll meet at the boat.
IDK what it will be like for you but last year there were some really good deals on oceanfront - not beachfront - condos in that area. We found a nice 2br, newly refurbished with quality stuff - $700/wk. Many of the owners mentioned that they were trying to help in the down economy by reducing their rates. IDK anything about the hotels in that area since we don't stay in them but there are several nearby and 2-3 mi. farther south in Keahou. From the condos nearest to Kona you can walk to town - there's a sidewalk/path along the road. Here's a listing of many of them - anything along Ali'i drive is your target area.
VRBO® is Vacation Rentals By Owner
In that area - mostly a short drive to the south - you'll find about 5-6 shore dives - a shore drive south to the Place of Refuge - one dive everyone tries to do. You can see on the map here how most sites are clustered in that area with a few north or south. The Big Island lives up to it's name - driving across island takes several hours.
http://www.shorediving.com/Earth/Hawaii/TBI/index.htm
North of the boat harbor is the airport - then a 20mile stretch of seaside driving - mostly along lava fields - until you get to Waikoloa which is where a few of the larger resorts (Marriott, Hilton etc.) are located. I mention it since you indicate you might want a hotel. The Hilton is the one with the dolphin encounter. Also the beaches tend to be nicer in that area. If you want to shoredive there though you'll probably have to drive north to Puako. There's not a lot of dining options in Waikoloa either outside of the resorts and only one operator that keeps a boat nearby afaik - the 20min. drive back to Kona gets old after a day or two.