Having lived in Cairns for 6 years I dived with Taka, Spirit of Freedom, Undesea Explorer and Mike Ball's Spoilsport. Some operators invoke "Queensland law" when they are just lazy - there is very little in the regulations (apparently) which restrict diving. (On one day-boat they refused to let me use a weightbelt while snorkelling - with a wet suit...)
I think Taka had a 50 minute rule at one time so they could adhere to their schedule; even I didn't find it too restrictive. They are geared more to the backpacker market.
What I love about Spoilsport (apart from the professionism of everything and a great crew) is that with a very modest try-out, they will let you dive alone with a pony bottle - a far better buddy than any photographer. So for photographers it's ideal, and at a place like Challenger Bay, I can sit at 6m for 75 minutes without a problem.
November/December would be my pick for the very best time of year. I wish I was going.
(Caveat - Mike is a pal of mine.)