1. I've gone diving in Okinawa in a 3mm shorty and I was fine, but I'm also fine in 23 C water with a dive skin, i.e. similar to shorts and rashguard.
2. I've dove with SeaSir and Piranha Divers. SeaSir is in Naha, though they have branches on other islands nearby. Piranha Divers is in Onna.
SeaSir - full service, i.e. they carry and setup the equipment for you. You only have to help rinse the gear at the end of the day. The boat is fairly large, like a yacht. Giant stride or ladder entry, with ladder reboarding. Passengers are a mixture of snorkelers, Discovery Divers and certified divers with quite a varying degree of experience. Fun dive groups are upwards of eight, buddy system. The boat goes out to the Kerama Islands, about 1.5 hours away. After the first dive, there's lunch (provided), then the second dive. Dive sites were pretty shallow, as there were Discovery Divers they have to manage too. In my opinion, for experienced divers, it wasn't very interesting.
Piranha Divers - small operation and you'll be setting up your own equipment. The boat is also small, so backroll into the water and small ladder to get aboard. I only did the U.S.S. Emmons dive with them. First dive, followed by two hour surface interval for lunch (you buy at a shop everyone walks to), then second dive. The destroyer is at 36-45m, so being comfortable at that depth is important, along with knowledge that you'll need two safety stops due to going into deco. I would love to repeat these dives one day.
3. I'm cheap, so stayed at a 1000 yen/day hostel. It was as basic as you can get.
4. Kerama Islands - maybe leave Okinawa a base yourself on one of the Kerama Islands?
U.S.S. Emmons - just an amazing dive, but it's not done often
