We were on the Western cruise in Sept. with an almost 6 year old DS and 7 year old DD. We normally don't book tours through the ship, because it's a lot cheaper - and in many cases better - to do things on our own.
In Grand Cayman, when you get off the tenders, there are many locals standing around offering tours. We took one of these tours which took us to Hell, and the Turtle Farm (lots of fun for the kids - not only do they see lots of different turtles, but they also get to pick them up), and then we got dropped off at Seven Mile beach which is a beautiful beach. The cost was $15/adult and half price for kids. When we were done with the beach we caught a "bus" (which is just a van) back to town for $2.50/person.
In Cozumel we took a taxi for $10 each way to Chankanaab. Entrance fee is $10/adult, kids are free. The sea lion show is an additional $5/adult, kids are free. Chankanaab is a very nice park. They have snorkeling and also a little beach area which is great for young kids. They also have botanical gardens with trails. But for us, the highlight of Chankanaab was the sea lion show. It's a really fun show that the kids will love. Afterwards, you can buy pictures of your kids kissing a sea lion.
You didn't ask about Key West, but the aquarium at feeding time is a really fun place, and in the evening, the cat show outside the Hilton is a must see.