mmh... wait a min.
ok, I don't have the perfect "recipe" to make great heads, but I know what i did wrong, at least

first, the Nathalie Portman head, done with splines:

you can see it looks nothing like the real "thing". And still the shape is perfect. The rule with splines, that I didn't find out then: use quads as much as possible, no triangles if you can avoid them. Refine if needed, adding verts won't hurt that much.
second, still with splines, my Grey head:

See? using quads only gives you much better results, no crappy edges or anything ( I didn't apply the relax modifier there, so there's still a few "sharp" areas, but with it, it's perfect ). ok, admitedly, non human characters are easier to do anyway.
third and last, my lachdanan character, w/o the cell shading crap:

done from a cube, poly extrusion, 1 tesselate, 1 mesh smooth.
my best human head so far if you ask me, done in... less than 20 minutes! Really, for now, LPM is unmatched if you ask me ( haven't really tried patch modelling yet tho ).
voila
