Moties
The Moties were fascinating in the way that they were a threat to humanity.
Hamilton's Laymil in the Night's Dawn Trilogy were interesting with their triple gender and their choice of species suicide as a solution to the reality disfunction.
Vinge's aliens are interesting but quite humanlike in their thought processes. The spiders in Deepness were definitely humanlike and the doggy things were more alien but still, their goals were similar to humans.