Since it's your first time on Coz., maybe forgoing the Yucatan trip completely and spending time getting to know the island may be a better use of time.
Rent a car/jeep/trekker and spend a day exploring the Cozumel, spend time on a secluded beach, visit the original town of El Cedral, Punt Sur Park, the many beach restaurant/bars along the Caribbean side of the island, the ruins of San Gervesio are a larger site than most people think and although not nearly as impressive as Chichen Itza, or even Tulum, they are a great place to kick off mayan studies, some very interesting history there.
There's also the much overlooked museum & the mexican market is cool to visit, just a few blocks inland from the town square (plaza). Not sure how much Chankanaab Park has been rebuilt, but they used to have a nice botanical garden.
If your still interested in going to the Yucatan, see the post Shepman refered to, I've been to all 3 major sites that most people go to and have put my 2 pesos in on the peninsula ruins.
ALL good options there, Tulum the most accessible, Chichen Itza the most impressive and Coba, not as excavated, but, if your are into it, just plane cool.
I'm branching out this April and going to Ek Balam!!! whoo hoo!!