Actually, for less than $600 (I've seen it for ~$550 I think...) the Sony DSC-P1 is an incredible camera. Look at these shots: http://www.dpreview.com/gallery/sonydscp1_samples/ .
The camera itself is 4.5 x 2.1 x 1.7 inches, and weighs 8.8 ounces including the battery pack. That's less than half the size of a large index card. It's smaller than a small index card. And it weighs half a pound including the battery... but still turns out better pics than the high-end digital cameras from a year ago or even more recently. AND it does mpeg movies. Yikes.
Update: Here's a picture to illustrate its small size.