Dude, there's a ton of stuff!
Mauna Kea is the place to check out. There are roads all over the place. And on a Mountain Bike you can ride to the top:
http://www.steephill.tv/2006/mauna-kea/Also ive always look at the road which goes from Waimea up on the side and around Mauna Kea. It'll spit you out just above the visitor center which sits at 9000ft.
Unfortunately as you alluded to there are not many good maps.
I'm not sure if you can ride there, but there are some beautiful hiking trail in the valleys to the west of Hawi.
For a ride closer to Kona, check out the roads which go upslope from 180 and Holualoa. the pavement usually ends at a gate and from there they head up Hualalai.
If you want a nice beach camping trip ask around how to get to Makalawena.