On Costa Maya, you don't have to book thru the cruise ship. If you want to see Chaccoben ruins (newly discovered, not commercialized yet) you can just go off the ship, thru the little artificial village, and near the taxi stand is a standup podium. They will take you on a tour for $45 compared to the ship's $72 in airconditioned van with English speaking driver. Only difference is he doesn't tour you over the ruins -- you do it on your own.
Echo and endorse the recommendation on Captain Marvins. Book on your own thru their website -- captainmarvins.com.
It was FABULOUS!!