I'd say there are 3 important points with cameras: The lens, the sensor and the processing of the sensor output, ie. the picture.
If you go for the compact cameras, they will typically have a 1/2.5" sensor (smallest sensor used in real cameras). I think the optimum number of megapixels for those currently lies around 5-7 MPs. With more MPs you risk more noise, as the individual pixels are smaller - they collect less light each, resulting in less signal compared to the circuit & sensor noise. For instance, a 5 year old (or so) 3MP Olympus UZ730 has very little noise at ISO 400 compared to a recent 10MP Canon G7 on which the 400 setting has limited value.
Dealing with this might in turn require more noise suppression processing in the camera (RAW mode for external processing is uncommon on compacts), which can tend to blur pictures a bit.
In the smallest cameras it is also difficult to make a lens small and cheaply enough, which is sharp enough to resolve that many pixels. At some point you just get the lens imperfections resolved in more detail. Professional SLR cameras have 24x36mm (full-frame) or half size sensors - much much larger, but still "only" 10-20 MPs.
Likewise, 18x zoom is indeed very impressive (have tried 10x - great for animals), but if you are interested in sharpness and uniform pictures, 5-8x zoom often fares better.
The Canon A710IS (7MP, 6x zoom) gets good critique, especially compared to its 10MP big brother, the G7. It also has an (emergency) optical viewfinder as a last resort and runs on two normal AA batteries.
With that slight criticism of today's compact digicams, I'd have to say that Olympus 510 sounds great.