Was in Utila in April. dove with BICD and UDC... Highly HIGHLY recommend diving with Bay Island College of Diving. All dive costs are set by the island government, so no matter where you dive you will pay the same price.
But... some of the less expensive places to stay are even cheaper if you dive at thier dive shop (ie, $3.50 instead of $5.00 a night for a room) You make the call if better gear, better staff, better boats, and better feeling of safety are worth it moentarily to you. They were to me, I dove at BICD.
so moving on... Both BICD and UDC have EANx, although the day i dove at UDC, they mixed my tanks about 2 min before we got on the boat... i wasn't too cool with that... Both have a PADI course director on staff (if that's important.) and they are the only 2 on the island (well, were when i was there)
north side is where the whale sharks are, boats really only run northside in the morning. I did see a whale shark when I was there, but from everyone i talked to, that week we were the only boat to see one...
Have fun!