The “salad” creatures from the Star Trek, Catspaw episode. Strings and all. Still freaked me out as a kid.
One of my fave series.
One alien race in particular are the Kelgians, which resemble eight-foot-long furry catapillars. The fur is emotion-expressive and is constantly in motion, always showing the individuals mental state plain as day (at least to another Kelgian). A Kelgian therefore always knows what another Kelgian is feeling and often thinking; consequently, Kelgians always say what’s on the their minds, and have no concept of deception or even tact. 
The Vorlons are a good choice.
I am also a fan of The Orz from Star Control II. They look pretty much like fish or whatever, but they are extremely alien and mysterious in all ways, mostly because the automatic translator can’t do a very good job and you’re left guessing what their intentions, motivations, behaviors, and such actually are. It is hinted that they are extra-dimensional projections into our own space-time with experimental and nefarious purposes. Doesn’t get much more alien than that.
The Crystalline Entity was decent enough, for TNG. A giant glass coral reef that eats souls’ll do that.
The Black Cloud probably beats it, though.
(Giant floaty things are very alien. 'Well known fact.)
I like ones where the mindset is alien (even if the physiology isn’t always) (C.J. Cherryh’s aliens are often good for this - the methane-breathers have already been mentioned. There’s also the seemingly very humanoid atevi in the Foreigner series.)
Others whose aliens I love (or rather, who I love because of their aliens, amongst other reasons) include David Brin in his Uplift series, Hal Clement (Mesklinites already mentioned, but I especially love the Tenebrans from Close to Critical,) and Iain M. Banks (the Affront and Dwellers especially)
James Tiptree, Jr./Alice Sheldon’s unnamed alien in Love Is the Plan the Plan Is Death is my personal favourite. One of my all-time best SF shorts.
The ants from Empire of the Ants. They’re “mere” earthly ants, but their thought processes, social organization and so on are weird as hell (and yet more or less scientifically exact, except for the whole individual thought bit).
[QUOTE=deadtwo99]
It is hinted that they are extra-dimensional projections into our own space-time with experimental and nefarious purposes. Doesn’t get much more alien than that.
[/QUOTE]
Reminds me of the old Stars! game, where you could setup your race to be 2D beings, which made them super good at fitting lots of them inside a colony ship and infiltration. The idea was that only 2 of their dimensions coincided with our own, while the rest of them existed in a parallel (or possibly orthogonal) universe.
I think that the OP is conflating two traits that are not necessarily linked, but often found explored together in the same stories.
The first is to look for non-humanform aliens. These are the aliens that look alien. That aren’t someone in a rubber suit, or with ear or forehead prosthetics. They show up far a lot for reasons both good and bad all through all varieties of SF. Most of these have been touched upon by other posters in this thread, and I wouldn’t dare quibble with those points.
The other trait is to look for aliens with non-human-patterned thinking. Which is a lot more challenging to present, and a lot easier to get wrong than right. You can have utterly alien biologies producing races of individuals that are straight cognates from various inspirations in human anthropology.
The much mentioned cheela, for example, are about the size of a slug, mass as much as a human, and respond and think in ways that are very easy for the reader and the human characters in the book, to follow. There are many cases of mis-interpreted cues between the two cultures, but none of it results from an outright inability to comprehend the others, as opposed to a mistaken understanding. I found the cheela to be utterly charming, and aside from their make-up, utterly human-like in their minds.
The alien blobs in Forward’s Rocheworld, however, were quite satisfyingly alien to me. Pushing what I’d consider standard thinking in ways that were quite enterating and thoughtful.
One of the best alien aliens I remember is from Roger MacBride Allen’s Ring of Charon series of books. The Charonians were alien in both biology, and mentality - with such a massive disparity in signal interpretation between the humans and the Charonians that effecitive communication between the two seemed impossible. In particular, Allen’s Charonians actually were pushing both definitions of intelligent alien life, with their blending of biological and mechanical aspects; and their rigid worldview, making it possible to question whether they were sentient in any true sense of the word.
Another intersting set of aliens are Robert Frezza’s Blues from Cain’s Land. Humanoid aliens, evolved from near monkey cognates, their culture at the time of first contact was sufficiently bizarre to the humans involved, that communications between the two groups was hugely strained. The author made it clear that in his opinion the idea of an incomprehensible biological alien did not make sense to him, but at the same time, within the frame of a human-like thinking mind, variations of biology and society could produce quite a few massive difficulties to communications.
I’d say H.P. Lovecraft’s Öld Ones". They have no interest in, or regard for humans. Sort of autistic aliens.
They have the voice of a wooden surf-dude? Terrifying!
I would nominate those triangular pancake-like cave-dwellers from the some lonely crystalline cave-system in Kurt Vonnegut’s ‘The Sirens of Titan’. That ends up as a surprisingly poignant chapter.
The Outsiders are quite a bit stranger, though. They look more like a cat-o’-nine-tails than anything else, and they are solar powered (but need to be a long way from the sun - round about the orbit of Neptune or Pluto is fine, where they can lie with one end in the sunlight and the other in shadow). They are extremely fragile, travel on spaceships that can reach relativistic speeds without the passengers experiencing acceleration, and make their living trading knowledge, on which they will sell anything to anyone if the price is right - though the price for any personal information about their own species is extremely high.
Then there are Anne McCaffrey’s Corviki, from The Ship Who Sang. IIRC (it’s a long time since I read it) they are giant jellyfish-like balloon creatures who live in the upper atmosphere of a gas giant, communicating through a combination of telepathy and colour changes. They can make host bodies available to visitors, including humans, even including the deformed humans who, like Helva, function as a spaceship’s brain.
Notable example:
"The Jophur
The Jophur are a fictional extraterrestrial race from Uplift Universe. Physically, they are a stack of waxy, living rings. Each ring serves a different purpose, and they connect to each other to form a single being by chemical means via an electrically conductive, sap-like substance that flows down the center to bind the stack together. A Master ring provides a strong sense of individuality to each stack and enforces this with corrective electrical shocks to non-compliant rings."
I’ve always liked the Amnion in SR Donaldson’s Gap cycle for good alien-y weirdness.
Would the novelty-vomit creatures from ST:TOS Operation: Annihiliate! count? If I remember correctly (and I very well may not), those things acted as one mass intelligence, taking over planet after planet.
I remember in the film Contact with Jodie Foster, the alien seemed to actually partially inhabit another dimension. It was only when he got close that he morphed into an image of Foster’s character’s father. The explanation was “it’s easier for you to relate to this form”.
J.
The Bajoran Prophets from DS9 are pretty alien, though they appeared as humans to Sisko and others. They exist in all times at once and have no concept of chronology, and live in a wormhole connecting one point in the galaxy to another thousands of light years away.
China Miéville has some interesting ones, like the Ariekei from Embassytown - all their tech is biological, so they’ll have little creatures that follow them like batteries. They’ve got spider legs, hooves at the ends of them, and two wings, one that’s kind of like an arm and the other that has the ears and eye antlers. They also have two types of mouths that harmonize speech, and the only way humans can interact with them is by engineering telepathic twins that can approach their speech patterns by speaking at the same time in two different tones.
Well, I’m interested in both kinds of alienness, really, though you’re right that they aren’t necessarily linked (although an interstellar cloud of sentient gas will be more likely to have a truly alien set of motives than, say, a reptile dude with many of the same needs to fulfill that us ape-guys have).
I’d vote for Orson Scott Cards buggers (and later piggies) in the Ender series before it went off the rails. Those were both pretty strange, especially from a psychology perspective. The aliens in John Ringo’s Legacy of the Aldenata are also pretty weird, both in form and in psychology and temperament.
ETA: WRT Star Trek, there were some pretty strange non-humanoid critters. I remember the rock monster things as being kind of strange, as well as the creature that could suck all the salt out of a person.
??? You can get a subtitled version of Stalker on DVD from Amazon…
Niven/Pournell Moties - 3 armed people that are amazingly superspecialized and range from tiny not actually intelligent ones that can repair and modify equipment up to their ruling class types, diplomats and so forth.
Drake/Flint Belisarius series - Humanity has changed and in the future portions of the book have almost unchanged normal earth type humans through types that have been modified to live on other planets with specialized environmental needs to giant stellar whale sort of aliens, to Aide - a crystalline non-DNA based person that did not start out human but ended up with human type emotions and behaviors.
Frederick Pohl’s Heechee, very interesting books.