What about the Pentax Optio:
W20 http://www.dpreview.com/news/0608/06080701pentaxw20.asp

I have the 6 MP version of this camera, it takes great pics & video i small enough to fit in my pocket and you can take some under water pics or vids with it (it is water resistant up to 5ft. for 30 minutes.) :-)