While AAing, don't be afraid to cut into the outline. Don't over AA, or you'll basically be doing a pixel-by-pixel blur. It should feel smoother and stay feeling thin. This is generally speaking, of course (in art, yes, rules are broken, and pixel art is still art).
The shapes and designs of those heads are really interesting (weird, in a good way).