If you really must get use an 8-bit PIC, and must find a functional equilevant of the 328P, then find a PIC18 with:
- 2kB RAM
- 16k or 32k FLASH words
- 12/16MIPS (although, if this is really critical, go for an another architecture instead)
- Works at 5V too..
If I do a quick search, you probably end up with a PIC18F26K22/K80.
From my experience, AVR and PIC are basically the same. I don't mind PIC's, but in general I find AVR's easier to pick up and play with.
PIC's sometimes have a scratch-your-head-for-some-time-why-this-doesn't-work problem, although that could also be experience with the devices..
However, the principles of both chips are the same. They have a CPU that runs instructions (although architectures differ), with peripherals that have a couple of registers that need to be set correctly. Both provide documentation on how to do that, and that's about it.
Moving to a PIC24/dsPIC33/PIC32 is not much different.. the CPU's run faster, more memory, the devices typically get bigger (because they tend to be used for bigger applications), and contain more peripherals/features. There are (plenty) of devices still available in DIP though.
ARM is a bit different, with a different architecture, more advanced and has it's advantages and disadvantages. If you really want to learn something different, pickup an ARM toolchain & devboard.