In fact we went during off peak so we spent less than half an hour playing n walking on the beach, though we did get to enjoy the beautiful sights..
The world's second largest aquarium is in Okinawa and it was awesome! We got to see whale sharks, manta rays and so many other species. It took my breath away, absolutely and I can safely say your kids and you would love it. There was a great dolphin show- free.
If you visit during January, like I did, you can take a boat out for whale-watching.
We also visited the pineapple park, where my child got to "drive" her own pineapple cart. It was kind of touristy though.
We drove to various castle sites/ruins, many being unesco sites. You can consider driving to the hiji waterfalls and some of the capes and cliffs. A lot of information available if you google.
We also went to the gyokusendo limestone cave at Okinawa world. It was quite a sight and experience! If you have kids that like snakes, there is a snake museum at the same place.
If you have any interest in beers, I believe you can visit the breweries in Okinawa as well.
We did a fair bit of shopping at Naha main place, toys r us and American village. My favorite shopping was at the supermarkets though, and I grabbed lots of yummy Japanese strawberries.
I am not sure if I gave enough information. But you can always google for more..

As for hotels, you can consider the Marriott and Busena. And my piece of advice is to get a car so you get to see more!