"You probably have researched Okinawa 10x as much as me."
Not really, as soon as I saw how much it cost to go anywhere on the main island I stopped looking!
Ruled out Ishigaki and Miyako islands as they cost 10,000Avios each way instead of 7,500 from Tokyo
This was more of a bish, bash, bosh job.
Looked up hiking (bish!), looked up onsen (hence the kumejima/ojima flirtation - bash) and then realised snorkelling was on the table (bosh! - Zamami!!)
The rest is just refining the details.
Once at Naha, the cost per adult per day for 5 days including accommodation, ferry travel, monorail, breakfasts, dinners as well as an onsen admission and all you can eat lunch is 7,000yen.
I am fully satisfied with all the choices that had to be renounced to arrive at this one. A hackett knife can be your best friend in the tropics!