"Best, Cheapest and Smallest" doesn't always come in the same package.

There's a whole heap of PICs that will do what you want, probably starting with the 16F628 (which is real easy to work with for a beginner) working up with more RAM and more features. Bare PIC chips are only a couple of $ (or less).

PICBasic Pro is easiest for a newbe - it's also the most expensive, but then again you pay for the integral features, it's stability and maturity.

If you go with PICBasic Pro (or it's cut-down little brother PICBasic which is a little more difficult to use due to it's stripped-down spartan way of doing things) then you are in the right forum.

Your existing PICAXE Basic isn't too distant from PICBasic Pro (looks like your learning curve should be about 30 Seconds), that, along with a suitable PIC programmer would probably your biggest investment. Go to the MeLabs website www.melabs.com or one of their distributors, set yourself up with what you need and we'll see you back here with either stories of success or requests for help. I'm sure if you're buying a complete outfit, any of them will throw in some PICs into the bundle to get you started for free if you asked.