For PICs, the OTP parts are the xxCxxx, and the reprogrammables are xxFxxx. Unless the "C" part has a glass window, in which case it's UV-eraseable.
the PIC16F84A is expensive and crappy.
A modern ... [like] 16F628
Yes. Except that the 16F628 is now also getting old. Microchip has a nice (?) habit of introducing new and better chips at lower prices, while keeping the old ones around at higher prices. The latest recommendation I saw for a beginner PIC was the 16F1827; it has the new "enhanced" core that gets rid of some of the more annoying points of the old PIC architectures.
Others advocate skipping the 16f series entirely and going to 18f or 24f...
Microchip is historically very nice about sending free samples. I'm not sure about Wales, though...