For a start (and maybe all the time?) you should look at the EEPROM/FLASH PIC's. The 16F84 suggested was a good choice a while back, but it's basically obselete now - you are better off using the 16F628, it's pin compatible with the 84, but costs less and has far more features.
The 16F628 was the chip I choose for my PIC tutorial series, although I cover some other ones as well.
As also suggested, the 16F877 is a good 'higher end' choice, but is a bit on the large size - the 16F876 is basically the same chip in a smaller case, with a few pins less (the 876 usually costs more than the 877, but it's often worth it for the size saving).
For the smaller PIC's, the 8 pin 12F675 is nice, it's FLASH programmable, and even includes 10 bit A2D inputs - it also used the same 14 bit core as the other chips above.