I was going to chime in with the GIMP myself, but it's not limited to Linux and similar Unix-like environments. I dumped Windows some considerable time ago, but I was definitely running the GIMP natively on Windows before I did. It ran just fine.
It's a bit of an odd duck interface wise, and I will admit that the most important reason why I run the GIMP is because it's the only application in its class for Linux. I'm not sure I can see myself getting and using the thing if I still had other choices.
OTOH, it's completely free (politically, and a price of $0.00) and very powerful. It can do some seriously cool stuff, and can easily go head to head with PSP. It's not a full-blown mega editor like Photoshop, but you won't find a better editor anywhere at this price. Especially not one that runs on all three of the most common PC operating systems.