I've never been a fan of all-in-one robot kits, even as a kid, so I tend toward places that I can actually get the widget I need, and then cobble things together myself. Here is where I'm currently doing my shopping:
Solarbotics - I live in the same city as these guys (Calgary) and I like to buy local, so it's really nice that they are a friendly bunch, and they actually do some fun work in the community, and have their own designs. Check out the Ardweeny, or if you want an afternoon project, the Useless Machine.
RobotShop.ca - I'm not a huge fan of overpaying for customs and shipping from the US stores, so I always check here for things I can't get from Solarbotics; they ship from Canada, so... YAY!
The two US stores below I have used, and both have reasonable shipping, and both survived the trip through customs without me having to pay double what I expected to.
Sparkfun - Easily the most down-in-the-weeds geeky site if you really want to know the dirt on that $20 sensor you're about to buy. Does it work they way you thought? Does it work at all? Each product has a discussion thread which is super-duper helpful. And the New Product Post videos on Fridays... nice!
Adafruit - Not 100% robotics, but one of the coolest places on the 'net. They have a ton of tutorials, are super-organized, and the different parts are actually intended to work together, which sort of hints at the genius lurking there.
ServoCity - I haven't tried these guys yet, but I do need a bucket or so of the types of parts they sell, so it won't be long now before I order. Anyone order from them before?