In my opinion, Gimp is just as useful (powerful?) as Photoshop. I don't know what Paint.net has, but Gimp has a bunch of effects like bump mapping, lighting effects, seamless edges, and such. The one thing I find bad about Gimp is the abundance of bugs (maybe I messed up some settings ). Sometimes when I try to bumpmap an image, it applies the map as if I had bumpmapped a different image that I have open at the same time. Also, the even numbered brush sizes scale up to odd numbers, so you have to put your brussh in the middle of two pixels. Other than those 2 things that I have found, Gimp is amazing.
I'd recommend GIMP, but i may be biased because i do other graphical stuff besides pixel art.
If you're starting out, in the log run, it'll probably pay off to get familiarized with the more advanced program. The GUI takes some getting used to, but it's manageable. BUT! Make sure you get the 2.6 version. They messed up the saving behavior big time in the newer ones.
As a starter, I would recommend Paint.net. A lot of people are recommending GIMP, and while it may have it's share of advantages, the advantages, and the program itself, are for more intermediate graphics designers, while paint.net is more new-user friendly. I say this from a Paint Shop user's standpoint, and while I find Paint Shop better than all the other editors I've seen, it costs money, which you probably aren't looking to pay for your first.
This is what I would suggest:
- Try Paint.net
- Once you're comfortable with graphics design, try GIMP
- Decide which one fits you best
- If you get to a point that you are really interested in graphics design, try the available free trial versions of Corel Paint Shop and Adobe Photo Shop. I use Corel Paint Shop right now, and I couldn't switch to any other, but that's my style.