Si quieres buena calidad, a opinión personal sobre cámaras de fotos, no me saldría de Nikon-Canon-Sony. No soy ningún experto de cámaras, pero a mi humilde parecer en estos tres fabricantes están por encima en cámaras digitales (igual hay alguna otra buena, pero me olvido). Olympus, pentax... en calidad las pondría por detrás, y luego ya están las marcas vetadas, hp, kodak, fuji, supratech, airis... eso nunca

.
Quizás una canon ixus 60 o ixus 70 más nueva te vaya bien, son pequeñitas y echan buenas fotos.
Tiene más megapíxeles de los que pides, pero mirate una Sony Cibershot H3. Es uno de los modelos nuevos de sony, y de tamaño es bastante reducida y es lo más parecido a una cámara grande de esas buenas que puedas encontrar. El objetivo es muy grande, tiene un zoom óptico increible y las fotos salen con una calidad del 15. De precio juraría haberla visto rondando los 300€.
De nikon no te sé decir algún modelo en concreto por que las últimas que he visto de tipo compacta me parecen feas todas por que las hacen gordotas, creo que las de serie S son finitas, échales un vistacillo, por que las de serie L que creo que son las gordas son feas a más no poder

.