My main camera is a Canon Powershot Pro 1, which is fantastic but sadly long since discontinued and not replaced by Canon. That kind of thing is probably a bit OTT anyway if your wife prefers a simple point & shoot.
I bought my wife a Fuji F11 last year, which has turned out to be very good. It's extremely small, works well in full auto mode, but retains full manual controls. The main benefit of the Fujis is their good higher ISO performance, which means you can shoot successfully in lower light than most compacts without resorting to flash. It's better than my Canon in this respect, even if it can't compete in overall flexibility and lens quality. The only things I don't like about the Fuji are the limited range of the lens (not really a surprise for a very compact camera), and the fiddly adapter block arrangement for charging the battery or connecting to a PC. It was just about to be replaced by a new model (F30 I think) when I bought it, but I haven't really kept up with progress since then.
Even if you can get an SLR for your budget, I personally wouldn't recommend one unless you're really serious about your photography. Unquestionably SLRs give you better image quality than compacts and allow you to get pictures that just wouldn't be possible with a smaller camera. On the other hand, the best camera for the job is always the one you happen to be carrying with you, and from my experience with film SLRs it takes commitment to carry around a big bag with lots of lenses, whereas a camera that fits in your pocket is never a problem. Just a personal opinion before the flames come in!
Second the recommendations for DPReview and Steve's Digicams. Both great review sites, and DPReview also has a great forum with lots of knowledgeable people.
The main thing to do is use reviews & recommendations to work up a shortlist, then get down to some bricks & mortar shops and actually handle the cameras. It's surprising how much you can get turned on or off a camera just by what it feels like to use, and I think that's more important than check boxes on feature lists. If nothing else, you can get the wife to come with you and get some revenge for being dragged around clothes shops in the past.