Well I've used Photoshop and PSP in various versions since the early days of both. I've stuck with PSP because it's what I got used to initially.
Whichever package you choose, you'll only need about 20% of what either is capable of. I find Photoshop, big, slow, unwieldy and heavy in it's use of system resources compared to Paint Shop Pro7 with which I do nearly all my stuff, although I have later versions which I don't bother with as they just seem to get flashier, more graphic in presentation, but don't have that much more to offer when you get right down to it.
Paint Shop Pro has now been taken over by Corel, and I'm just trialling the latest version - Paint Shop Pro X2, which is getting big, slow and cumbersome - I wont be taking it up.
As someone said Photoshop is the one in most common use, and the one you'll probably get most member advice for if you need it. Other than that, all I'd say is pick a package and stick with it for a while at least, as swapping and changing in the early stages can be very confusing.