These are the ones I have kept installed and find useful. I've only tested freebies and there's a load of others I tried but, they either didn't add/improve anything that's in this lot, they had poor performance/stability issues for me, or they were just plain crap. If I find any more worth noting I'll add them here. Also, I'm using these on an Apad tablet running android 1.5, so some stability and performance problems I had may not affect use on a phone.
Paint Pro (ElectricSheep) - Free.
There's 3 versions of this Paint, Paint Pro, and Multi Touch Paint. Haven't tried the multi touch because I don't have a multi touch screen. Paint Pro is the same as Paint but with the addition of some options like undo/redo, so don't bother with the non pro one.
The word "pro" in the title is a little optimistic. Very basic options but ok for sketching. Can change background colour for canvas. Colour wheel for brush colour, but no settings for value, saturation, or opacity. Basic round hard brush, soft edged brush, embossed brush, with a slider to adjust size. No opacity sadly. Eraser. Can save and import images.
Draw and Share (EVTGroup) - Free.
I've been using this one more than any of the others listed here because it does the job nicely. It's very quick and responsive to brush strokes. Has a colour wheel, with sliders for opacity and brightness. Slider for brush size, and soft and hard edge brush. Has undo/redo, import/save, add text (and silly clipart from a small selection available), clear canvas. No Nonsense, simple and reliable.
Peintureroid (SAkira) - Free and Paid.
Only one I've tried that has layers (think the free version is restricted to 3). Can open saved images, and can import images to layers. Undo (but only for last step). Apparently has multi touch support but I can't test that. Colour palette (hue, value, and saturation), unlike all the others I've tried the colour palette can also remain open while painting allowing colour picking on the fly. Also has eye dropper with the palette to pick colour from image. Zoom in/out, and canvas move. Brush size and opacity (called density here) sliders, eraser and 5 presets (same brush it seems, but different colours), not sure if you can use these to store your own brush settings to reuse later.
I like this one a lot now but haven't used it much until a very recent upgrade fixed some reliability problems. The brush has a nice brushy feel with thin to thick strokes, very responsive with no lag. I've noticed some stepping in strokes as the width increases along a stroke, but for painting it's not that noticeable.
Paint Joy (Bejoy Mobile) - Free and Paid.
Nice range of brush types and shapes in this one (Paid version has even more apparently), with a slider to change size. Nice colour palette (similar to the style of palette in Peintureroid instead of the usual colour wheel most use), and options for opacity, saturation, value. Can save, but no import option. Has zoom in/out and move canvas. Records a video of your painting session (don't think you can save it out though, at leat in the free version). This would be my favourite if it was more stable (I suffer from random crashes at the moment), so I'm hoping a future update will fix that. If the paid version was available to me in the market I'd happily buy it.
Graffi (Ibo-Soft) - Free.
There's several versions of this including a paid "Pro" version. They all seem pretty much the same but the one just called Graffi has no adverts in it, so it's the one I stuck with.
I find this one a bit laggy on my tablet. Has some interesting brush options including filled areas, embossed strokes, shadows and so on (Paint Joy has a few of these brush types too). Has a colour wheel and sliders for brush opacity, size, brightness. Can save and import, undo/redo.
Sketcher (wargoth) - Free.
Drawing app ported from the procedural, web based, sketching prog Harmony (http://mrdoob.com/projects/harmony/). A little on the slow laggy side for me but fun to play around with as you can get some nice effects. Can save and import. No Undo.
(there's another similar, app like this called Draw(er) but I haven't been able to get my hands on it to try it).
AndroPaint Lite (tecxten) - Free.
Another one that lags for me but still useful. As well as painting, this one has some image processing options, filters, cropping, canvas size, and a load of others. Has soft and hard edged brushes (round and square), brush size slider, hue/saturation/value/opacity, fill, shapes (circle/oval/square/rounded square/line), text. You can cut, move, and paste, resize parts of the image. Eraser, undo, import, export as jpg/png. Bit like a mini Photoshop this.
PicSay (shinycore) - Free and Paid.
Image processor not a paint app, but it has a load of effects filters (like a very cool liquify-esque distort tool for one), can add text (and more silly clipart), and has some transformation tools.
CamPainter (Arming Mobile) - Free and Paid.
This one has a slight lag on brush strokes but is still very usable and nice to work with. Canvas size can be set from a range of presets up to 1024x768 (pro version can change canvas colour). Nice colour wheel with hue, value, opacity, and also shows the current colour as well as the new one you are selecting. Good colour picker showing which colour you are selecting from the canvas. Brush slider for size, but only allows 3 preset sizes (pro version seems to have variable size brushes though). Undo/redo. Zoom in and out, and has a very useful navigation window on screen when zoomed in (like Photoshop's). Can import image directly from camera, as well as standard file import and export (has an auto save function too). The pro (paid) version has a canvas grid.