Oh yes, names are such a pain to make out. Random generators might be useful there with some changes afterwards.
As for history, you could consider such questions: for how long your species has been developed? (That is also the length of their history) Were they people waging wars or more peaceful folks, asking questions before killing? Did they discover space travel centuries ago or was it only a recent discovery? Were there changes in the society, the behaviour, the beliefs, along the course of history? A turning point in history?
I tend to believe the Biologic part is the hardest, what can you say about the organism of an alien species? There isn't much to say usually, except if your Empire is featuring subspecies for instance. Or perhaps I am not imaginative about such fields.