I don't really do much pixel-based work anymore, so my art program of choice is Inkscape. Once you get used to it, it's a wonderful tool for making vector-based images.

But if I had to pick, I'd go with GIMP because I was actually able to understand it, unlike Photoshop which I didn't (and also it was shareware, so yeah). But nowadays I use Paint.net whenever I need to do pixel work. It supports layers, can view multiple images at once. It's no GIMP / Photoshop, but it's a great step up from MS Paint, and that's good enough for me.
_________________________