Thanks for pointing out Tux Paint! I think I've heard of it before, but for some reason never bothered installing it. My daughter enjoys it, so how can I complain?
I learned quickly that it really is necessary to run it in full-screen mode. And it saves files as PNG, which is cool. I recommend downloading the "rubber stamps" too. Good stuff.