You mentioned that you have a simple probability system for the randomization of the faces. Have you thought about controlling the correlation between features? For instance if the face is boot shaped there is a 90% chance the ears are fin shaped, but if it's flop shaped then there's a 80% chance it has horns instead.
Viewing post in Making Martian Faces comments
The system itself does support species like that but I haven't loaded it up with much yet. It's more-or-less based on some ideas from Papers Please, where what you really want is to define some criteria, then generate papers (or a face) that explicitly matches or does not match in interesting, non-confusing ways.