We love Cozumel! We have traveled there several times a year for the past 6 years.
I have heard nothing but great things about your Op and the hotel. We like to dive with Albatros Charters (www.albatroscharters.com
), its a small company that has 2 boats that can go into the marine park. We usually stay at a small condominium, Casa Martillo in town.
On your first dive trip to Cozumel, I would concentrate on just Cozumel. Dive everyday, have lunch, relax and have a great dinner. In between visit the east side, go to the beach, get a massage, and enjoy a few cervasas. Go to the square on Sunday night. No need to get back on the ferry and go to Playa or Tulum.
Great places to have dinner. Our favorites are Kinta, Pie de Carbon, ElPique and Los Oatates. Most do not open until 7pm.
We always rent a car, we like the freedom that gives us. We rent from Rentadora Isis, just google the name to find the web site, Margarita, the owner is terrific. Always get the Mexican insurance, it will save you big time if you have an accident. We know from an experience! DO NOT rent a scooter, it can be very dangerous!
As far as dive sites, its all great for us. We love Columbia Shallows, its only 30 feet tops but is very beautiful. Any of the Palancar dives are spectacular. Try to dive north at Barracuda, its usually a quick current. Do a night dive at Paradise, we saw 6 octopus and much more in May.
Have a great trip whatever you decide to do!