I think to get the most out of your plunge into your first home theater purchase, you should figure out what you want to buy and how much do you want to speand.
I would recommend first listening to speakers...but you need to decide if you want to buy a 5.1 system, a 2.1 system (what I've got), a 3.1 system...etc etc. Go to several speaker stores in your area and just listen. Bring in some of your favorite CD's and listen to as many different brands as you can. For further recommendations, check out the speaker message board on here, you'll find plenty of options & opinions at all price ranges.
If your budget for speakers is under $1000, I think you'll find that just about any of the receivers recommended above will be fine. While some would disagree, I don't think you'll hear much of a difference in different receivers, especially in the $500 and below categories. I'd go more for the features that you find important (for example, do you plan on running your cable box, xbox, & dvd player all through your receiver? does your TV have HDMI or DVI?...etc etc).
While all of this can be overwhelming for some. Just spending a little time really figuring out what you want to get can yield some nice dividends. You'll feel better about your purchases and you'll be more prepared as you get the never ending urge to upgrade.