Well, my family and I just got back from Palau and it was a hoot. We dove with Sam's Tours and we really enjoyed their professionalism, their dive guides (we especially liked Dexter, Jim, and Petra), their flexibility (my wife and daughter both had health issues to work around), and their quadruple-filtered water. Their bag lunches, though, leave plenty to be desired.
We saw large sharks, mostly grey reef, on every dive -- more than 15 at one time on Peleliu Express, alone. There were also tons of red-toothed trigger fish, giant schools of pyramid butterfly fish, lots of jacks, dogtooth tuna, sweetlips, titan triggerfish, turtles (7 on one dive), and, of course, the jellyfish in Jellyfish Lake. There was probably a bunch of little stuff, too, but most every dive being a drift dive meant that we couldn't slow down much to look.
We dove several really cool dive sites during our 8 dive days. We particularly liked Jellyfish Lake, Ulong channel, the Jake seaplane, Turtle wall, Dexter's wall and the various dives out at Peleliu. Blue Hole was also surprisingly pretty. Blue Corner wasn't at full boil but that was okay since we got all the adrenalin we could ask for out of Peleliu Express.
Palau has to have the prettiest top-side vistas on the planet. My whole family loved the trips to and from the dive sites through the lush, green rock islands. We also liked Kraemer's restaurant (several people recommended the Taj, but we liked the chicken masala at the Seahorse better).
On the down side, the sites were way too crowded (though, we were warned). Often, dive sites would have 13 boats or more, all with divers in the water. We even had to abort a trip to Blue Corner because there were too many divers in the way. Boat traffic throughout the trip was so bad that divers couldn't just surface -- we ended up going a little into deco on one dive so that we could surface safely with the group.
I think it's important to note that this is not a destination for people who are newly certified. My family each had between 120 and 140 dives and, except for once incurring a small deco obligation, handled the strong currents, upwellings/downwellings, blue water safety stops, and surfacing restrictions with little or no drama. We did see a couple divers, however, who didn't have the skills for the dives they were making. I think it would have been helpful if they had been warned in advance.
The funny thing about this trip was that we went into it having heard for years that Palau is the best dive on the planet, thus giving this site a lot to live up to. It is possible that no location could have compared favorably with everything we've heard. I think my wife and I also approached this trip with a little trepidation after the diver death at Blue Corner a couple years back. Palau's got some excellent diving but I still think Fiji is our favorite -- particularly in light of a $800 per person difference in airfare just to get there. While we had loads of fun (modulo health issues that weren't the fault of Palau or Sam's Tours), I think we ended up being just a little disappointed.