Been there done that ;) You can get yourself AVR chip - go for bigger flash/ram version like ATMega32 or ATMega64, this will allow you not to think too much about memory constraints in the begining.
All you need is a breadboard, a chip, some pin headers and a programmer hardware. As for programmer hardware, something cheap and simple as USBasp will do, or you can get yourself Litle Wire which is a bit more than just a programmer.
If you want to run chip faster, get a crystal and a couple of caps.
Build environment is open source and rock solid, available for most popular platforms.
You could look into ARM platform too, chip like LPC1343 does not require external hardware to program it, but it comes in smd packages only, so you'd need to make a PCB yourself or get a ready made platform like Forebrain or mbed
What's nice about mentioned ARM platforms is that you get native USB interface.
PIC microcontrollers can be programmed in C too. I'm not experienced enought to talk about that, but in general you need the same as in AVR case.
Edit
I've noticed, you mention microprocessor in your question. I suspect, you are really interested in microcontrollers as these are integrated, microprocessors require more hardware knowledge to begin with.