Ah, that's a very intruiging question - to which we probably won't get any better answer that what we can come up with through speculation...
It's really, really hard to extrapolate from n=1 intelligent species, but as you suggest, there may be some universals; some things I would consider in coming up with a credible alien intelligence:
Then there's the fact that certain traits may make it much more likely to encounter aliens that have them - if they don't have the need or curiosity to go beyond their home ground, it's much less likely you would encounter them.
I feel however that it is really hard to think about so very different minds. While I don't subscribe to his non-reductionist views of the mind, Thomas Nagel's What is it like to be a bat? is a classic in this area, as it's reprinted in The Mind's I.
Anyway, good luck writing your fiction!
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.