Anywhere along about a 80 mile stretch centered on the west side is great for shore diving. Air fills is another matter. I'd recommend staying in the Kailua Town area (main town south of the airport) for access to dive shops, and number of shore dive sites. North of there - Waikaloa and Puako as mentioned - doesn't have nearly the number of shops or shore-accessible sites, but what's available is probably adequate. There are a handful of sites down beyond Cook/Kealakekua that are really good, but only one air fill station that I know of, the Euro-shop at Kealakekua town. To me it's quite different between Kailua town and the Kohala area up north - weather, seas, amenities, lodging - so for a month that's something to consider.
I'm in Kailua now and had one week of the flattest wind and sea conditions I've ever experienced here, and now one week where one or two afternoons the surf and wind were up a bit. Not one day where everything was closed out, by any means. I don't think there's a really reliable rule of thumb over the short haul, but I've spent several 2-6 week trips here over the winter, and more days than not of good shore diving has been the rule.
