If the budget is $400-600, either of the Onkyo receivers will take up almost half of it unless you can find a good deal on a refurbished model. You might do better choosing one of the 50x series. They now include HDMI switching (but not upconversion from other analog video formats) and nearly all of the features you are likely to need, especially when you are just starting and haven't accumulated a lot of other devices.
Bookshelf speakers are just fine but really need a subwoofer. Towers extend much lower in frequency response and although a subwoofer is still an important addition, you can get away without one for a very long time if you buy towers.
The surround speakers are less critical than all the others, so if possible I'd get two towers and a center channel. These three speakers really need to match for the best results and if you get just the towers first, you may be unlucky and find that the matching center will no longer be available when you are ready to get one.
Used/refurbished is a good way to go as you can often get a really good deal. I intend to upgrade my speakers when some of the new models I'm considering are released. I'll end up selling my JBL towers and center for a pittance - probably under $200. You could very well find a decent deal like that if you look - Ebay, Craigslist, classified ads, etc.