We did cavern tours with Aldora, who laid on a van and driver on the mainland. But you can very easily also book with a mainland dive op. It is not a big deal to go over on the ferry, and many dive ops will pick you up in Playa del Carmen. Aquanauts (Dennis Weeks) enjoys a superb reputation for running cavern tours. Dennis is a cave instructor as well.
German taught my cavern and Intro classes, and he's a delightful man and I'm sure he does very good tours. I dove Aerolito as a cave dive this last trip, and it's fascinating, but I'm not sure how much cavern there was, and it's quite silty, so you need very good skills to dive it comfortably.
As far as cenotes to see, I think most operators go to a fairly set group of places. Ponderosa has some very nice cavern, as does Taj Maha (with some lovely light effects from the halocline). Grand Cenote has a ton of decorations, and Dos Ojos has some stunning white limestone.
A serious warning . . . You either won't be thrilled with the dives, or you'll be hooked, and if you're hooked, you have an expensive road ahead of you (she says, having just finished Cave 1 and a second week-long trip to Mexico already this year, and planning the third one).
