The Canon S3 is well worth a consideration. The super macro mode is helpful and the video output is outstanding. The catch, though, is that there isn't a manufacturer UW housing for this model so you'll have to turn to third-party housings which usually cost an arm and a leg.
Just finished a Sipadan trip using that housed in an Ikelite. Have a look
here.