The three smallest 35mm full frame cameras are the XA's, the Stylus and the Minox. Although individual dimensions vary (e.g. the Minox is taller, but not as thick when closed) they are essentially the same volume. The Minox is a classic clamshell design, so it is much bigger with the lens door open and the lens pulled out. The Minox also has a shoe on top, so it can snag on a pocket. Both the XA's and Stylus use Olympus' classic "sliding dust barrier" so they are the same size opened as closed. With the Stylus you also get a built in flash.
I haven't had the best of luck with the Minox shutters as they get older. The Olympus' seem much more dependable, as befits a camera built by the gods.
How about a Pentax Auto 110? It's ridiculous how tiny it is, yet it's a legitimate SLR with a reasonable variety of interchangeable lenses available.
If you want great image quality and you want to be able to put it in your pocket there aren't that many cameras that fit the bill. I disagree on the XA and the Yashica T4 and the other second tier P&S's. I don't think the lenses are all that stellar. The lens on the T4 for example is contrasty but not all that sharp when you get into the negative. The images just don't hold up upon enlargement unfortunately. I personally would pass on the Rollei 35 if you don't want your pants to fall down. It is pretty heavy. The miniature Minoxes are fun to use as a novelty (I have one and am probably going to buy a slitter for it) but seriously lack in picture quality unless you are only looking to print 4x6's. The Ricoh GR1 is thin enough to put it in your jeans pocket and the lens is absolutely top notch. Until it died I used it instead of buying a 28mm for my Leica. The lens is that good. It is probably the best all around pocketable camera. I don't want to blow hundreds on a pocket camera again so after a lot of looking I decided to give the Minox 35 a try. I have one coming.
^ I agree with the above sentiments on the Ricoh GR1 which if my memory is correct I upgraded to after trading in an Olympus XA in 1997. The GR1 lasted only one week before it was killed off in a freak wave on the beach where I left it on top of my t-shirt while I had a swim. You know what happened! I do recall the lens being exceptionally sharp. After that upsetting mishap it was back to finding another XA, which I secured in the autumn of 2000 and kept that until 2005. I don't see many second-hand GR1 specimens about; people are either holding on to them as one of Ricoh's finest, or they are just sparsely distributed. I'm very happy with my XA and the first prints were exceptionally sharp, well exposed.