At first I thought about just going with the cruise line sponsored trips but the more I think about the more I want to go out on my own, like you we've never been on a cruise either...
Although I know this thread is a little old, I do want to provide my 2 cents as I just returned from a Mediterranean cruise.
My cruise ship, Celebrity Century, offered one dive excursion on this trip. It was for a dive trip out of Dubrovnik, Croatia. Given that I'd just received the latest Scuba Diving magazine listing Croatia among "Europe's 8 Best Dive Destinations" I booked.
The day before we arrived in Croatia, the cruise ship advised me that due to lack of participation, my dive trip was canceled.
I believe if I'd booked with reputable local dive shop I would be writing about my first dive in the Adriatic versus my canceled trip.