CyDive is very reputable in Paphos, then again Dive In is very reputable all over the island
If you get the chance try to dive Jubilee shoal in Avdimou and St. George's island in Latsi. Both places are near Paphos but don't miss the Zenobia for any of the two. I'll second Digger's idea of going there with a car (if you're renting one) and meeting in Larnaca either Rob from Dive Tek Cyprus or the meet with the guys from Dive In Larnaca.