Mike,
The receiver you have is a very nice receiver and should do well with just about any speakers.
With a budget of $1500 you have a couple different routes you can take. You can either buy all your speakers at once for the $1500 budget or your can buy a couple now of higher quality and then add as money premits. If you want to buy all the speakers now, I would look at Boston Acoustics, Athena, Paradigm, Energy, PSB, Infinty and polk just to name a few. You also might want to look at internet companies like Axiom, Cambridge, Rocket, Swan and even Nohr. You can usually find some really good package deals with internet companies.
If you want to just buy maybe a center channel and two mains you can buy a lot more speaker. Start buy looking at the same brands mentioned above but look at higher lines of speakers. Then as money allows, you can add a sub and rears for 5.1 6.1 or 7.1. I really think this is the best way to go. You have a top end A/V receiver, why waste it on cheaper speakers?
My personal preference is Boston Acoustics. My Boston setup really shines with my Yamaha receiver. I find they compliment each other very nicely. The Yamaha is a very detailed receiver IMO and the Boston's have a warmer sound IMO. To me, the match is perfect. But that's just me. Other opinions will differ. The key is to get what you like.
One thing, 12 x 18 is a fairly big room. Don't skimp on the sub. Look at HSU, SVS, Paradigm to name a few.
Shinerman.
