Sketches of Q is the name of my favorite sketching app. It was written to run on Sharp’s Linux-based Zaurus PDA. The features that make it stand out, are:
The canvas is actually twice the resolution of the screen, and as you draw, it draws onto the larger canvas, which is then scaled down smoothly to give nice smooth, sketchy lines
The paint bucket tool: Instead of instantly filling all connected areas, ink would slowly pour out as long as you held the pen on the screen. This let you fill shapes that weren’t completely closed
I’ve duplicated the first feature in a proof-of-concept app for Nintendo’s DS handheld. It's a bit slow, and touchscreen support is not perfect. And no color selector. But I like it so far.