Hi Peter,
In terms of great value for money, Kangaroo can't be beaten at $AU470 for 3/2 11 dive package. The crew are friendly and laid back, the food is generally good and the dive sites, especially at Milln and Briggs Reefs, are great quality.
I worked as an Instructor for Cairns Dive Centre for a year back in 2005 and am constantly going back to visit them when we have some time. They have a max of 35 pax but you will generally find somewhere between about 25-30 onboard. They also have just had a refit, which is nice.
I can't speak directly for ProDive, but they seem to be a good bunch as are most of the dive operators in Cairns. Admittedly they are a bit more expensive at $600. They run monohull boats also, which in swell can be a pain in the butt to be aboard, but that's about the only gripe I could think of.
Oceanquest is a new boat I think, or very much upgraded. They are leaning toward the 600 dollar mark, some of the dive sites eg Norman and Saxon are great (I think they go there) but the Hastings reefs are average.
If you need any more info, not that i can tell you a whole load, but just let me know!
Nemo