I bought a Canon s110 (now s200) for my wife for her birthday last year. It's a 2.1mp camera, but it's really small and light.

Our first trip with it was to Rome, actually, and it worked great. It does take small video clips w/sound - 15 secs on high quality, 1min on low. It also has a fully metal body so it is hard to ding up/break etc. It's smaller than a pack of cigarettes. I did buy an extra battery and a 128mb card. Should be less than $400 for all.

Everyone we show it to is amazed...had a whole pub crowded around us in Ireland!

The sony's are nice, but more expensive and bigger/heavier.

Greg