I still think you should go a little more above your price range and get a dslr. Like clothing, they are an investment, and like good shoes, they can be resoled. Actually, that comparison doesn't work. Basically, after you get this guy, you are stuck with it in present form. You can't upgrade it...you want more, you need to buy a new camera. A dslr is upgradable. Want a better camera? Get a new lens. You can actually build your camera "wardrobe." So...imagine an upgradable Edward Green instead of a static Johnston & Murphy.
I have a D90
and my wife has a D80
You can find both used for just a little above your budget (400 probably...500 max). I've bought all my lenses used and never had a problem, and I know several people who have purchased their camera bodies used and have had no problem. I don't know about buying a used camera online, but Phoenix is a big city...I guarantee that with a little bit of digging you can find a brick and mortar store which sells new and used cameras.
That being said PaS are less of a hassle to deal with, but if your GF loves cameras, I'm sure she'll be more than happy to show you how to use a dslr.