You really shouldn't have to prebook but when you first arrive check out a couple of shops, see how they run their operation, how their boats look, ask a few questions. Find out how busy they are. Once you've found the operator of your choice, if they are quite busy then maybe you should book your block of dives at that time just to be sure.
If you plan on doing a bunch of diving, you should be able to get a better rate on a block of dives. You'll want to ask about that too, especially if you plan to do any of the day trips out to the Atolls. Those trips are more expensive but you can get a discount on them too if you've been doing a bunch of stuff with the same shop.
My recommendation is Amigos del Mar but there are other good operators too.
Most all of the operators will pick you up at your dock, no matter where you are staying.
A fish and a bird can fall in love, but where will they build their nest?