As photobearsam mentions, even better photographers occasionally get red-eye. A major factor in acquiring red-eye is the positioning of the flash with regards to the lens. The closer the two are, the more likely you'll find red-eye. Not guaranteed, but the odds go up.
You're looking for a small camera...which almost by definition will have a close lens and flash. I'm not an expert on 35mm point and shoots, but beyond the 'red-eye' function, look for a camera which has a pop-up or swing-out flash. Our Kodak APS has this flip-up (I think they call it cobra something or another) flash, and compared to our old p&s's, we do get alot less red-eye.
The Canon elph family are really small cameras, but they use the APS format. The film and processing can be signicantly more expensive depending on where you get your processing done. To keep our APS costs down, we usually only buy Fuji film when it's on sale at CVS and then take it to Sam's 1hour processing. For us, the 1-hour processing for double prints is as much as we'd pay for 1 hour processing of 35mm at most drug stores, with the added benefit that the girls working at the Sam's near us are 'regulars' and we have a rapport with them.
The APS/35mm debate is a very deeply religious matter for some people. We use both.
One last thing to keep in mind...the smaller the camera, the more steady your hands need to be. Especially when you're in a situation which requires a flash. The shutter speed will be (usually) that much slower when the flash is required. That's why we bought the slightly larger Kodak aps p&s instead of the much more totable elph.
When we do get red-eye, we use a red-eye pen to take care of it...works reasonably well, so long as you don't mind _everyone_ having the same eye color.
I hope this helps,
Joe