The biggest problem with selecting an instructor by word of mouth, is that most every new diver loved their first instructor. After all, when one is just starting out, how can one know any better? There's no way for a new diver to compare. So, a new diver's recommendation, is only that they liked their instructor. Kinda like the Stockholm Syndrome.
Therefore, generally the best thing to do, is once you have arrived, go around to the shops, get a sense of the shop(s), and meet the person(s)that could be your instructor if you chose them. Have a conversation, ask some questions, get a sense of how you will relate with them, how the two of you will communicate, and so on. Then make your pick . . .or you could just select one in advance, go with that and I'm sure you'll still be very satisfied.
It's what you do with your diving after you are certified that will really count. Just as when you first got your driver's licence was the beginning of learning to be a good driver, an Open Water Certification is the beginning of learning how to be a good diver.