Before going on a trip I make up a list of likely looking dive ops, based on their website, personal comments by buddies, and what I see posted on places like Scubaboard.
When arriving at the destination, I go down to the docks and check out the boats. You can tell a lot about an operation by looking carefully at how the boat is setup and maintained. Particularly in non-US locations, I end up rejecting a few operators based upon the condition of their boat.
Often, I'll dive with more than one operator in area. Different operators have different advantages --- one may give the best marine life briefing in the world; another may go to a particular site I want to visit that day; on a rough water day a big cattleboat may be best.
It's rare that an operator is so bad that I wouldn't consider using them again.