I will second on the arduino from sparkfun. At the moment I get the lillypad (an arduino variation) or the arduino mini pro, both around $20, but the lilly pad has pins already on it for the serial/power to usb thing that you will also want to buy.
I am not a big fan of the avr instruction set, so I will throw in that you can also get the armmite pro, arduino footprint but arm based. The mbed is relatively popular, super easy to use and you dont need anything else (the other two mentioned want for a serial to usb adapter for programming and power).
right now TI is pretty much giving away msp430 launchpad boards for $4.30 or $5 something at sparkfun, just through in a couple with the order. the msp430 is a good instruction set, no harder or easier than anything else to program. (they are all easy once you get the hang of it)
At the ti website there are the stellaris boards, loaded with gadgets like oled displays and things like that, it is trivial to brick the 811 board so I would recommend one of the others, the 1976 or whatever that number was wasnt a bad board, good price/feature for getting your feet wet.
All of the above have sandboxes to play in but you are not required or limited to the toolchains, programmers, host operating systems, etc.
I am not a pic fan from a product perspective, I cut my teeth as you are about to do, using a pic. but moved away and never went back. there are some boards at sparkfun for the pic. I have not tried the propeller, I prefer chips I can program directly instead of an on-board interpreted basic or anything like that (I reprogram my arduinos and armmite pros as soon as I get them to wipe the interpreter and take over).
I think the arduino is probably the place to start to meet your description, there are many flavors now and partly because atmel does a very good job with documentation/support and perhaps for that reason there have been avr fanatics/lovers, and as a result of that there are TONS of hobby DIY projects that are arduino based. With an arduino I think you will hit the ground running sooner than you would with another platform (even the ones I mentioned).
Microcontroller