Although it is expensive, I think the PIC16F84A-04/P is a good choice for the first few projects. Don't forget the 2 capacitors to ground from the crystal (15-33pF datasheet section 6.2). It's very simple, there are a lot of tutorials for it, and most of what you learn can be used for the whole midrange PIC range.
The PIC12F509 is probably not a bad choice if you find a decent tutorial, but it is lacking interrupts which are a good thing to learn early.
The PIC12F509 is probably not a bad choice if you find a decent tutorial, but it is lacking interrupts which are a good thing to learn early.