Cozumel... what a great place to go dive.
I stayed at the Barracuda. Small cheap dive hotel, $82 / night for double occupancy. But very quaint, clean, and I'll definitely stay there again next time. I was travelling with some people who stayed at El Presidente. Over $400 / night and it wasn't even all-inclusive. Very very nice rooms, good but overpriced food. And way out of town. Having seen both extremes I'll definitely be staying at the barracuda again. Barracuda is about 5 blocks to the square and an easy walk. El Presidente was about a ten minute taxi ride out of town.
Here's the rundown. You absolutely MUST have a hotel with a dock. The reason is that you simply tell your dive operator which hotel you're staying at and they pull up to your hotel's dock at roughly 8-9'ish in the morning and pick you up from your hotel. They drop you off in the evening, and after rinsing out your gear (Barracuda has a freshwater tub outside just for this) you head into town for the evening. I took several taxis around town, and never spent more than $4 for a ride, but you still can't match the service level of getting picked up and dropped off at your own hotel's dock. Now, depending on where you dive you might want to go back to your hotel for lunch, or get dropped off somewhere nice to eat. When we went all the way back to our hotel we only had about 15 minutes for lunch, but when we asked to be dropped off at the presidente, we had over an hour for lunch.
Dive boats seem about 50/50 between two different styles. Either small 6-8 diver boats, or 30+ diver "cattle boats". I much prefer the smaller ones. I dove with "Deep Blue Cozumel Extended Range Diving", and heartily recommend them. They seem to have more experienced divers as customers. Our entire boat had computers, we all had our own equipment, and we just basically hit the water and dove 4 dives per day without any hassle. Try
http://deepbluecozumel.com or +52 (987) 872-56-53 and they'll take good care of you. The owner, Mark I think, made sure that we hit different sites on every single dive during our stay. You can pay $55 for a two-tank dive to the dive shop behind your hotel, who will then sub it out and get a "cattle boat" to come pick you up, or call Deep Blue (or one of the other good dive shops in town) and pay the same thing to go out with a group of 6-8 similarly experienced divers on a small fast boat. If you go Deep Blue please mention my name, because I'll be back there at least once more this year (and every year!)
Finally, one last plug. My travel agent for the trip was Carribean Dive Tours. +1 (770) 578-8028. Mention code H0075 so my dive shop gets credit for a referral. Diane knows every hotel on the island, every dive shop. You tell her what you want in terms of a hotel, she'll list all the hotels that meet your needs. She'll book the airfare, and if you want she'll book your dives. You pay the same thing you'd pay if you did the "legwork" yourself, but you get less trouble and you get free transfers to the hotel and back from the airport.
Enjoy!
P.S. I looked at the cozumel maps that someone else had recommended and they look great. I've got all three of their maps on order.