There are the aliens in Blindsight. Rot13 Spoiler: Jub ner rkgerzryl vagryyvtrag ohg ynpx pbafpvbhfarff.
I've got to agree, Blindsight is an excellent example. It successfully (IMHO) portrays aliens that are clearly quite intelligent, and yet utterly inhuman.
SPOILERS SPOILERS
The most frightening thing about them is that none of the usual tropes apply to them; mutual understanding and/or empathy isn't an option because their psychology (or possibly lack thereof) makes it completely impossible. There's nothing there to empathize with.
One of the most important points raised by the sequences is that not all minds are like humans. In quite a few places, people have discussed minds with slight changes from human minds, which seem altogether different. However, a lot of this discussion has been related to AI, as opposed to minds created by evolution. I'm trying to think of ways that minds which evolved, and are effective enough to start a civilization, could differ from humans'.
Three Worlds Collide would seem like an excellent starting point, but isn't actually very useful. As far as I recall, the Babyeaters might have learned their baby eating habits as a result of societal pressure. The main difference in their society seemed to be the assumption that people who disagreed with you were simply mistaken: this contrasts to humans' tendency to form rival groups, and assume everyone in the rival groups is evil. The Super-Happies had self modified, and so don't provide an example of an evolved mind.
So here are my ideas so far.