Picking a microcontroller
Although the PIC18F4550 is a decent uC and there are quite a few examples out there of using it for USB, it's still 8-bit and probably in the same "league" as your Arduino.  

If you want a bit more power, I would maybe look at the 16-bit PIC24/dsPIC (a lot more powerful and still available in through hole) or even the PIC32 (surface mount only though, and you would generally use C to program it)   

I thought the PicKit3 (I assume you are referring to this) was not too bad price wise as programmers go, but if you want cheaper you could go for the PicKit2, which although not officially supported anymore, will still be usable with 99% of Microchips range.
There are also many other decent programmers for PICs, for example the Embed Inc offerings - if you go for the 16-bit 3.3V parts I imagine the $25 LProg would be suitable.

Although online resources and a good related book (e.g. Learning to Fly the PIC24 - note this is C based) makes getting started easier, I would get used to reading the datasheets (and Family Reference Manual in the case of the PIC24/dsPIC) thoroughly, it is a necessary part of using any microcontroller and the only way (IMHO) to learn how to use them fully, especially the more complicated ones. Even the above book (though well written) misses out a lot of lower level detail.