If you like Deluxe Paint you might want to check out grafx2. It's a GPL licensed graphics program inspired by Deluxe Paint. I've been messing around with it a bit, and it's pretty cool. Would probably be useful for sprite art, or similar style art.

http://en.wikipedia.org/wiki/GrafX2 http://code.google.com/p/grafx2/