I'm a recent convert to Corel Photopaint. I picked up a copy of Corel 9 (Draw, Photopaint, etc) on Ebay a couple of months ago. I bought it for Draw, in fact, which I use for work - and found that Photopaint is an excellent program. Corel 8 and 9 are regularly on Ebay at around the 10-15 mark.

I had (still have) PSP 8 prior to that. It's a good program, and has a few more modern bells and whistles, it's true, but Photopaint doesn't choke on large images in the way PSP tends to.

For free, though, GIMP and Deep Paint are amazing.