To get decent music performance from an AV amp, you can't go wrong with the Arcams. Either the AVR500 or the AVR600 will do the job, and it may be that your choice of speaker will dictate which one you go for depending which side of your budget window you want to stick to.
Speakers are a very personal choice, and an audition is a must. But here goes anyway! To keep you within the lower side of your budget, I'd look at either the KEF XQ30AV package, or a package by PMC based on the GB1i, DB1MCi (ot TB2MCi), and DB1i for rears with a sub of your choice to keep within budget. Both of those would be with the AVR500.
At the higher end of your budget, you can base the system around the AVR600, which has a greater ability to drive more awkward speakers, and has pre-outs to allow the addition of a better power amp stage, not that we see anyone wanting to do this, unless they're using the AVR600 as a stepping stone towards the AV888/P777 combo. With this, you could look at the XQ40AV package, or a PMC system based around the FB1i, the TB2MCi centre speaker, and a pair of TB2i for rear duties. Again, subwoofer can be your choice - this really is dependent on the room size and what's needed to fill it.
Obviously if you're buying ex-demo or sale items, this could change again, but try and keep the speaker package balanced. In other words, if there's 2 centre speakers available, go for the one that uses the same size bass driver as the front pair, and choose rears in a similar way. Speaker packages like this will also perform extremely well for multi-channel music.
If you're after small speakers, then the type of package you're looking for will be different to above.
Normally, those that want the most from their 2 channel performance I'd recommed two seperate systems, but because the Arcam amps are so good at 2 channel music, I think most people wouldn't bother having a second audio system, unless they're extremely fussy about how they want their music to sound.