The AVR is way less important than the speakers are, especially in your price range. Any of the entry level Denon's, Onkyo's, or Yamaha's will do. But I would insist on hearing the speakers first. Everyone has different preferences, and the speakers make the biggest difference there. You can get incredibly good sound quality from a $1,000 budget as long as you avoid the 5.1 craze.
Best Buy's Magnolia is a decent way to sample different brand speakers to see if any stand out to your ears.. but the best places are the smaller shops that will carry brands like "Mcintosh" and "B&W" for example. If you live in bigger city you should have no problems finding a place like this, but they are much harder to find in more rural areas.
If you do, you could get something like 2x B&W 685's or Paradigm Monitor 5's (my recommendations for example.. but simply go with whatever sounds best to you) for $600, then a $200 subwoofer, $300 receiver and they can probably knock $100 off to fit your $1,000 budget. These types of places have always cut me a deal when I bought a complete setup and even thrown in all the speaker wire for free. That'll never happen at a major chain.