NotPete's long post - I'm doing biome first, and assigning traits based on that with re-rolls. I've got biomes grouped according to temperature and type, like hot forests and temperate wetlands. If it gets a tropical shrubland, then it will pick from scales, skin, and fur. Since it's a hot biome, then if it lands "fur" it'll re-roll, making fur less likely but not impossible. It re-rolls a lot of things based on two traits. 1) Biome, determines size, fat thickness, materials used like scale and fur, and certain parts like tusks are more common for shrublands and forests. 2) Aggressiveness, determines certain parts like horns for combat and less likely to have tusks, and wings are less likely for aggressive creatures. Because of this, animals are currently split into ~8 categories, based on biome group (no lake/ocean/rivers yet) and on aggro, but each category can vary wildly.
I've also go NO IDEA how to handle names! Right now the plan is to make a list of consonants and vowels, and to assign vowel-con-vowel-con-vowel. Urina and Afiko would fit.
Sentient creatures are very possible, I'm thinking that they'll be 1/3-1/4 of the time, and they'll be [CAN_SPEAK][CAN_LEARN] with [NO_EAT][NO_DRINK] added. To make them actually seem a bit intelligent, they'll be more likely to have [BUILDING_DESTROYER:1] for wooden doors and windows, and more likely to be beer thieves and such.
Underbellies - That's not really possible. I think it would be with some effort, but not really. To be perfectly honest, creatures in DF are a series of spheres attached to each other, with each sphere having layers like the earth's crust and junk shoved inside, like brains and livers and ribs. There's some vague idea of direction with left/right arms, which mostly helps determine gauntlet use I think, but it's supposed to help in wrestling and surprise attacks? There's not a good way to define an underbelly though. That being said, you can paint a false underbelly, by defining a body part named "underbelly" and then giving it an appearance, so you can have "she is red, her underbelly is white" but the underbelly wouldn't really be there.