- Smallness is all: Olympus XA, Minox, maybe Rollei 35.

- Very, very small but with some usual additional features: Yashica T3 (with a very good Carl Zeiss Tessar 35/2.8, a flash, a waist-level additional viewfinder and very good overall quality).

- Very small, a bit heavier, with manual exposure and a rangefinder: almost anyone of those: http://www.cameraquest.com/com35s.htm

- Still small, very versatile and high quality intechangeable lens, but more expensive:
Leica CL, Minolta CLE (Leica M mount) or Contax G/G2 (Contax G mount).