Right then: time for some further picks of mine, both of which feature some of the most alien aliens I've ever read about, and manage to make them convincing as people.

Vernor Vinge: A Fire Upon The Deep.
Vinge (again): A Deepness In The Sky. The prequel.

.... I won't precis them to death here: that'd be a waste of two (imho) thundering good reads.