I also thought the food was pretty good - buffet breakfasts and lunches with a fair amount of choice, and big cooked dinners, and endless snacks if you wanted them. If you have specific dietary requirements I would let them know, as there is nowhere to get fresh supplies after you are out there....
In terms of getting a spot, it depends on your time frame and risk tolerance! Basically we were there at Easter, and had pre-booked on Taka II, which was full for that trip, but there were plenty of places on other boats and other trips, and on the Taka II for all trips except the one we were on (over Easter weekend). You cannot pre book the cheap tickets though - have to turn up in Cairns and go to the dive shops/travel agents, of which there are hundreds. So if you have a bit of flexibility, and can wait a day or two to get on a boat, I would not book till you are there, as it is extremely unlikely you will not be able to get on a boat going out to Cod Hole/ Osprey Reef if that is what you are after.