Krita:
Slow as all hell in my PC at least, but seems pretty robust.
MyPaint:
http://mypaint.intilinux.com/ now at http://mypaint.org/
Very barebones GUI (in my opinion), but fast and decent feature wise.
SmoothDraw:
Much like MyPaint, basic GUI, but with a good performance; seems to have less features than MyPaint.
(added: Oct/2016)
FireAlpaca:
I’ve known it for a while, actually I knew it when I first wrote this post, for some reason I forgot to include it, must have wanted all the alpacaey goodness for myself.
It’s a drawing software, that has an alpaca as mascot.
Great performance and relatively lightweight.
Even has an easy to use vanishing point feature so you get the perspective right.
My go-to for quick doodling (I suck at drawing, doodling is as far as I go)