We went fishing in Cozumel on the first Western in May 2002. It was a bust. Something I hadn't thought about was the timing of a fishing charter vs. when you dock.
In Key West, you don't get in until mid-day. That would leave you with an early afternoon fishing session, unless you want to miss the sunset and fish in the evening (as I recall, you don't leave until nearly mid-night). Most fishing isn't very productive during the heat of the day. Check on Shirley's Key West thread to see if anyone's done it.
In Grand Cayman, you do get there a little earlier, so that would work out better, but I have never heard of anyone fishing there, so it might be tough to find information on it.
As I said above, the timing just really doesn't work out in Cozumel. If you really are set on it, research it (mini-golf Sally would be a good resource, she has a thread on the boards). We just walked off the boat and talked to one of the people on the dock. He sold a good story, but the "boat" was really small, with crew that didn't speak English. We had 4 rods, with minimal tackle. And all for a bargin price of $300 or so (have a mental block about this, since I got sea sick in the bargain!). We only hooked one fish, and it was on a loose line that our "guide" had just tied a hook onto and dropped in. Fish got off. Bottom line, we got what we deserved for not researching it, and buying the salesman's story.
On our 4 day cruise, DH booked the fishing excursion at
Castaway Cay and had a great time. Everyone on board hooked and brought in something, including a couple of sharks. The head server recommended it to us after our Cozumel disaster, but the boats weren't able to come in to CC on our first cruise, so we did it on the second. If you really want to fish, and you want to actually catch something, book CC bottom fishing!
Good luck!