Actually, I think the quality of the lens and optical zoom are far more important than megapixels. Just about anything unless it's really cheap is going to have at least 5 mps. Unless you're planning on blowing up all your photos into monster posters, that's plenty. More mps doesn't mean better pictures, just the ability to print larger ones.
I have the Powershot S51S, which is a great camera and not terribly expensive but it's a lot more camera than anyone needs who isn't a little bit experienced. However, if you want to go that route, it's very easy to use at the auto settings level, has all kinds of great options in auto and it has a 12x optical zoom, which is equivalent to a bit over 400mm lens. I really like the speed too. It's much faster shot to shot than my old Olympus. Of course the memory card can have an effect on that too.
And if you do really get into photography, it gives you the option of manual settings and some ability to add other lenses if you buy a converter. These cameras are the midline between a point and shoot and an SLR.
It's a nice, small camera too and lightweight but might be more than someone who wants a pocket camera would want to carry around.
By the way, one little tip for everyone. If you notice the quality of your photos going down, try replacing your memory card. They do get scratched and worn and that will have an impact on your photos.
