Hi. I live (and dive) on Okinawa.
I recommend Rich Ruth at Fathoms for at least one dives. He goes to the Keramas most every weekend, and if you are coming to Okinawa, you gotta go.
I don't know if you have looked into staying on Kadena, but I don't think non-military can. I've had problems trying to make reservations for non-Air Force, and since 11 Sep, you can't even get on base without a military ID or sponsor. But there is a place called the Cat's Inn (or Cat's Eye Inn). I think their rates are about 5000 Yen per night. If you e-mail Fathoms, I think Rich may be able to give you some info
As far as local dives, there are a ton of spots. If you don't have dive buddy, Kadena Marina does guided dives every Sat morning. They are AF, but the Marina is off base, so you can get access. I'm sure they'd take you along military or not. You can also check out a WEB site called H2Okinawa. They have a dive buddy data base.
SunFish, I'm pretty sure anyone can dive with Rich. If you are ever on Oki, I recommend him. He is X-military who took up permanent residence here. His shop is off base and not connected in any way to the military. A lot of us dive with him 'cause we like his boat dives.
Enjoy your trip.