Have you looked at the new Palm phone? [1] It looks like an ideal small phone, with a camera that, judging at least by the marketing copy, should be quite good. It's advertised as Verizon's exclusive, but at least in Europe you can get an unlocked version on Amazon.
[1] https://palm.com/pages/product