When I needed to create some pixel art for my last game, Antigen, I used DPaint 4 running on an emulator. I still hit DPaint keyboard shortcuts by accident in Photoshop.
Brilliance was even better, but never really got the same mindshare. (Possibly because it was quite a bit more expensive.)
Still haven't found anything as fun to use.
MVP Paint was a cool DOS clone. I really admired that little company for some reason.