I'd also suggest starting with one of the lower-end, popular uC's such as the PIC16F84A, PIC16F876A, and PIC16F877A.
There are so many documented projects using these parts online and in magazines (Elektor, Nuts & Volts, Everyday Practical Electronics, etc). Like with anything else, there's a certain learning curve and little things to be aware of when using these parts, and seeing other people's working projects/code can be very helpful.
For the programmer, I'd also suggest the PICkit 2. Buy the original, as it's often the same price or even cheaper ($40) than the clones. The PICkit 3 has been out for a while, but while adding new parts, it has dropped a lot of functionality (no more 3 channel logic analyzer, UART tool for monitoring serial comms, etc).
Here are two videos, one showing how to program a part with the PICkit 2, the other showing the logic analyzer (not available in the PICkit3).