The suggestion to go with the Monitor 9 is a good one, considering you'll be getting a sub. I still think that if it all possible, you should listen to other speaker brands as well, before making the commitment to the Paradigms. They are good speakers, but speaker preferences can be sooooo subjective, that it would be prudent to listen to others. If it's just not practical, you certainly won't be buying junk if you go ahead with the Paradigms, as they do offer great performance at the price.
A $500-$1000 budget for a receiver is a fairly wide range. With the area you have to fill with sound, I would go with the best receiver I could find for $1000. I'd certainly look for a sale for receivers that normally retail for $1300-$1400, just like my RX-V1800, which I got for $850, but normally retailed for $1200-$1300.