Echoing what was said above...
Start (again ) small, blinky LED, a few buttons, blah blah blah...
PBP and PICs are a bit of a leap from Stamps. Pick a PIC and get used to it. My choice would be an 18F4550. Sure, it's got a lot of bells and whistles, but you don't need any of that to start out with. And by the time you want to start using all those bells and whistles, you're all used to the ins-and-outs.
PBC vs. PBP - I'd go PBP right out of the gate. There's a lot more there to worry about, but then again, there's a lot more there to keep you from worrying about other things.
PBC is closer to the Stamp than PBP...but you're probably going to end up with PBP anyways right? The extra $$$ are WELL worth it.
Programmers - I'd go straight for the PICKIT2 direct from Microchip. $50-ish, and very well supported. And, with the new firmware, there's a 'LOGIC ANALYZER' built into it, along with a few other features which you can find at the website. And if you get the right package, you'll get a demo board with it. Mine came with a small board with a 16F887, 8 LEDs, potentiometer, push button, and a small prototyping area to tap into.
And agree 100% with the MikroElectronika boards. I don't have one myself, but if I ever wanted a prototyping board, one of those would be it.