The Canon G9 and G10 are quite well regarded. Same goes for the Olympus cameras. I think Canon's have an underwater setting which adds reds to the photo, which really helps.

I prefer a mechanical zoom to a digital one. Get as close to the subject as possible for the best color, and as long as you are close enough, use the flash where it always triggers, whether needed or not.

I know many have the Canon G9 and now 10 in an Ikelite housing, which allows them to later buy an add on strobe which really makes a difference, but you don't have to get a strobe right away, but the housing will support it.