GrafX2. It''s really good. Works a lot like Deluxe Paint II Enhanced. It still needs a bit more work to be really good, but hey, it''s free. A lot of demo graphicians use it.
Also, as a side note, you might want to check out Artgem. It''s got a pretty cool interface, supports layers, and truecolor It''s shareware though.