Photoforge,

I was amazed at just what the makers have managed to squeeze into this Ipod app its mind boggling:

Zoom which goes almost to pixel level.
Brushes eight of them each with opacity and size sliders.
Eraser.
Fill tool though it fills the whole screen not a section.
Color picker.
Smudge tool.
Clone tool, yeah that's right an actual working clone tool!
Crop tool which can rotate, flip the image and crop to any size.
Filters (like photoshop) which has: curves, noise reduction, unsharpen mask, sharpen, blur, simulated hdr, hue/saturation, brightness/contrast, exposure, vibrance, tilt shift, auto white balance, auto exposure and auto enhance.
Effect filters: dreamy, lomo, watercolor, oil painting, sepia, black and white, night vision, heat map, pencil, neon, emboss, sunset, bluesky and television.
Undo and redo (unlimited)
Save

All that and It even runs smoothly

Now what it does not have:

no export at all so no larger images.
no gallery or way to see what images you have already painted.
no playback of your painting.