Really, really small (but no manual controls of any kind)- I would recommend the Sony T series.
Smallish (some manual controls, OK image quality)- Canon A series; Really any of the SD series; or, if you can find it the Fuji F30/ or F31. Also, the Lumixes are great cameras, but their sensors are noisy as hell
Small (kinda- but excellent controls)- Canon G9; Nikon P80.
Say you have BIG pockets- Canon S5IS; Lumix FZ50.
If all you care about is awesome quality, but are scared of looking like a professional, and you are made of money- check out the Leica M8... or if it's only your left arm that's made of money, the Olympus 420 is the smallest DSLR currently made .