Obviously, there's Photoshop. I think you can download a trial of it to learn how to use it, but I'm telling you that the learning curve is a bit steep. However, learning Photoshop can really help, considering it is the industry standard.
Gimp is what some people call the "poor man's Photoshop," but it's not exactly like Photoshop either. It's similar, but it definitely could never replace it. However, considering it is free and it is a fairly powerful program, I say it's worth playing around with.
I've heard some great things about Paint Tool Sai, a pretty new program from Japan. It works wonderfully if you have a tablet, and it's very tiny too. The best part is how painterly the program looks. It's a little over $50 in US dollars.
I also recommend openCanvas 1.1, which is also free. It's a great program that packs a lot of punch for being so tiny. However, it can glitch.