Q:

Creating truly alien, intelligent NPC races

How can I make intelligent NPC races that are truly alien?
They need to be:

Culturally non-human.  They need to be stranger than any sort of human culture that already exists.
Rational.  Behaving completely randomly, or with no logical purpose would be non-human, but not meaningful.
Physically humanish.  The source of their weirdness shouldn't be something strange about their physiology, like having two heads or having a very strong sense of smell.  What makes them non-human should be mental, social, cultural.
Eventually understandable.  The PCs, after enough interaction with these creatures, should be able to understand their motivations and behavior.

A:

Creating an alien mindset is a matter of contrasting them with our own (else what are they "alien" to?), so what informs us?

Social – we break down in isolation
Tribal – we have a monkeysphere that limits our ability to grasp (or care about!) the scope of our actions' impact
Hunted – we are prey who just happen to have brained our way to the top of the food chain. We still think like prey, though: we're afraid of the dark and growly creatures.
Hunters and domesticators – we see our environment as a resource to be exploited
Vulnerable – we adapt our environment to suit us, we don't adapt to our environment. We're actually poorly-suited to most environments we find ourselves in.
Storytellers – our own and others' behaviours are only comprehensible to us by making stories about them, either implicitly as we think, or explicitly as we transmit culture.

Now, take one or two of those and change it. Keep the rest the same, so that you've got the basics of a framework that might be eventually comprehensible to a human. That's your method of making a person or culture truly alien while also possibly discoverable in principle.

For example, what if we change Social but not Tribal? Make a species of alien that developed from a prey-but-hunter species, that's vulnerable, and that have storyteller psychology. They evolved from a creature that was a loner, but somehow needed to (for territory and genetic purposes?) keep track of their kinship group. Their "social" interactions would be very aloof, possibly hostile or alarming, since they just don't need to care about the "social" impacts of their actions. They'd maybe be able to recite a geneology on demand, and might reference kinship relations the way we do politics. There would be an odd contrast to a human interlocutor though: they'd occasionally talk about "sisters" or "fathers", but in terms that contained no warmth and possibly with casual references to killing them off if they got inconvenient. Being storytellers, the internal politics and intra-familial colt/hot-war would be deep, tangled, and fascinating. Think Game of Thrones, but a species that doesn't understand the concept of remorse for causing others pain or injury.
As an exercise, pick one of the list above and change it to its opposite, and see what you come up with. The next one I'd be inspired to look at would be vulnerable, for example: what would a species be like if the concept of "shelter", "food", and other physical requirements were for some reason not in their hierarchy of needs, while keeping the rest more-or-less similar?

A:

I believe the most effective approach to this would be to build your species from the ground up.  When you try to make something "sufficiently alien", you are implicitly starting with humans as your baseline and making variations to that theme until it is different enough to meet your criteria.  While this approach may work, it's usually not very effective and doesn't have the dramatic results desired.
To build a completely alien race (or as alien as is comprehensible to our human minds), I think you need to consider the absolute essentials of a living being, decide what you want those to be, and go from there.  For example:

Every living organism requires energy in some form or fashion.  How does your organism acquire it?  (food, light, momentum, electricity, chemical reactions, background radiation... lots of possibilities) 
If more than one of these organisms exists or has existed, it must have a way of communicating.  How does it do so?
What environment fostered this creature?  Under what conditions did it evolve or come into existence?

Once your answer these kinds of basic questions, an alien psychology will naturally emerge as you consider their logical consequences.  To take humans as an example, we evolved on an ocean world teeming with other lifeforms, and that has dramatically shaped our experience of the universe.  We are social creatures because we had to group together to survive.  Our curiosity as a species is highly developed because our environment was so complicated that we had to know more in order to succeed as a species.  And so on and so forth.
Also, because our primordial threats were sensed mostly through hearing and seeing, the vast majority of people are auditory or visual learners.  These are the aspects of the universe we tend to focus on.
So let's say I was making an alien race.  I've decided I want this race to acquire energy by consuming gasses and performing a very small-scale nuclear fission on appropriate types.  And perhaps the biggest threat to this creature was ingesting gasses poisonous to it (methane, ammonia... perhaps even oxygen?).  Then its primary means of understanding the world might come through smell or taste rather than vision.  And this would fundamentally change that being's outlook on the world.  Think about it; everything in human culture is based on vision and audio.  What would a world look like if it were instead all based on taste and smell?  Very different.
There are lots of other questions you can ask about the origins of your alien race, and there are myriad possibilities.  But it's also important to remember the scientific limitations on life (as we understand them).  At some point, if you make a creature too alien, you've made something that simply could never exist or evolve.  Keeping this in mind, you need to strike a balance between deviating from the human circumstance/mindset and scientific plausibility.

A:

I'm going to take a slightly different direction here, zeroing in on your qualifier of "human-ish."
How human do you want them to be? I get that you don't want them to be just physiologically weird, but there's some fun things you can do with a creature that's 90% human. The key is that you should never just make a change to the base template of human and stop there. Really think about them, picture how this thing works, how it survives. In doing so, you're also going to have to change your expectations of its enviornment, but I'll get to that in a moment.
Let's take your example of having a very strong sense of smell. Humans have five senses (maybe more in your setting, be it telepathy, psionics, magic or whatever, but I'm going to run with the five) but not all senses are equal. We see first, hear second, touch a distant third, and while we can taste and smell we don't rely on them. It's not that we're bad at those last ones (well, we are) but it's that we don't find them useful, and that changes our society and culture. We very strongly favor sight in our culture. Example time: Cars, the primary form of transportation for Americans at least, are impossible to safely direct without sight, but all other senses can be pretty much ignored. Next time you're driving, think about what it would mean to have hearing be the dominant sense for humans -- instead of street signs, there would be speakers emitting a constant tone. Instead of changing streetlights, there would be different sounds depending on what everyone should be doing. Another example of the Hearer society -- how many times as a kid were you reminded to look at someone when they were talking to you? This is because most humans lip-read at least a little (how often do you say "Sorry, what was that?" on a phone as apposed to being face to face, even in a loud room?) and a lot of communication is nonverbal anyway. But the biggest reason for looking at people when you're talking to them is so that you can't focus on something else. Wherever our eyes are, that's what has our attention. Listening to other things is bad manners (headphones out of your ears please) but nobody minds if you're fiddling with an object (touch) smelling something good (smell) or eating while you're listening (taste). So a hearer society might not care where you were looking when you were speaking, but would be annoyed at background noise. I can imagine messing with the PCs of a game by having an NPC wander around the room while speaking, seemingly paying no attention to them. But that's not really alien is it? 
Back to smell. Lets take a human, but diminish sight to a peak at around 20/40 -- enough to legally drive, but barely. Boost smell up a bit, but we don't need as much as you'd think. Most humans can already distinguish where they are, who is near them, and what things might be in the area. Basically, lets just assume that Smellers can distinguish multiple scents at once, which is something that gives most humans trouble.
A human having a conversation with a Smeller might think they weren't taking them seriously. After all, the Smeller isn't looking at them, but wandering around the area nearby. It's still a spoken conversation, but this seems disrespectful, especially, when the Smeller turns their back on the human! This makes the human nervious, as the conversation is an important one.  (My friend has been kidnapped / the evil emperor is coming / etc.!) The human has just physically exerted himself by running away or fighting someone. Still, the human takes care not to allow his face to show his feelings. Suddenly, the Smeller takes a deep breath, and says "Why are you so afraid? Where are you hurt?" The Smeller is picking up on the scent of sweat that most humans pump out when we get nervous, or the scent of blood. Suddenly, the smeller looks surprised. "The emperor's guard are here!" The human looks around confused. He doesn't see anything. 
Societies would compound this difference. A good hiding place for your house key might not be under the welcome mat, but in the flowerpot. They might not bother to bury the key at all -- the fact that the flower hides the smell of it is the important thing. I'd love to make some PCs paranoid by 'hiding' a treasure in plain sight, surrounding it with air fresheners. Perfume woud be like wearing a mask. Since families smell a lot more alike than they look, there might be a stronger sense of clan unity as people don't differentiate among members of other families. If you've ever gotten in trouble with your significant other because they were upset but you didn't notice the body language cues, then picture that but with smell. An NPC Smeller could be pheromone-wise weeping his eyes out or making his hands into fists without the PCs noticing. How do Smellers drive? Certain scents probably have specific meanings -- much as red in america almost always means stop, I can imagine manure (and a specific kind too -- cow manure smells very different from chicken waste, which smells different from horse manure) means stop in Smellville. Strong wind causes you to slow down as location becomes harder to pinpoint.  
But this is still a fundamentally human thing. It's just interacting with its environment a bit differently, even if it might really confuse you. What can we do to change that? Three main ways occur to me.

Continue making assumptions as to how this would change their culture, and play up those changes. What if Smellers treated members of a family as functionally the same person? This grows out of the difficulty of distinguishing between people who live together, but that might very well be alien enough. It's not a hive mind (which, while cool, is a bit overdone) but could be creepy. The key here is to construct a set of rules that makes these creatures different from human normal behavior, with each rule tied directly to the physiological change (i.e., all members of a household are treated as the same person, because distinguishing individuals is difficult. Being unclean is a sign of strong disrespect, because it's offensive and makes you seem low class. (Imagine someone showed up to work in ripped jeans and a stained tee shirt.)). You want these rules to interact in interesting ways, but together create something that is very strange and different. This makes the culturally non-human, humanish, but clearly rational and eventually understandable. If you're spending a long time with these creatures, you might even make each rule a feature of a session. (The party is similar enough they smell the same, the rogue steals something and the cleric gets punished for it.) I'd think of at least five such rules, probably ten.
Make assumptions about how the individuals function, beyond the obvious. Yes, shifts in the wind would change what they're aware of -- so "I'd keep him upwind of you" would be an interesting idiom, but really we're looking for interesting individual behavior. They would move to keep themselves downwind of most people. Imagine during a conversation they just keep circling. They would be comfortable in dark places, something that will always set a human's teeth on edge. They would dislike rain and deep water. Swimming would probably be right out. Smell alone doesn't tell us much about this, but think about where they are on the predator/prey continoum. Are they group creatures or loners?  If they use technology, how much do they rely on it? (Technology isn't just cars, computers, and guns. If they have iron, or use spears or bows, that's technology too. Do they build houses?) Are they sexually dimorphous? Do they reproduce sexually at all, and if so are there only two sexes? (Going back to smell again, I could see having fun with an extremely sexually dimorphous creature whose dimorphism is not expressed in what the body looks like. No mammaries for females and a genital sheath for males, but with pheromones distinguishing them could mess with the players.)
Make assumptions about the environment. If they come from the same ecological niche as humans, they'd be the same as humans. Carnivorous species are always scary to humans, since they display what seems to be a lack of fear response to us. Plus, there's always something frightening about the fact that they might just eat us. Herbivorous creatures can be equally strange -- eyes on the side of the head, prone to run first and ask questions later. What kind of place do they come from? Here, you would impress the strangeness and alienness of the world on the players. Maybe everything has a natural camoflage? Maybe it's night twenty hours of a twenty-four hour day? Maybe most of the planet has tunnels beneath the surface where everything lives? If the aliens are not on their home planet when the players encounter them, what assumptions do the aliens make? "The wind is picking up. We must get inside before the acid rains." "They went into the forest. The plants will probably eat them." "Leave him. There is no saving the wounded, their blood will only draw more foes." This creates a culturally different, though seemingly human result that can be understood once the players see the enviorment they come from. 

There's a limit to how non-duck something that looks like a duck and quacks like a duck can be. The uncanny valley is your friend - something very close to human but fundamentally not can be even more strange than something that didn't look human to start with. You'd be surprised how much mileage you can get out of very small changes to the human body. Get rid of thumbs! (That will change how individuals function like crazy.) What if taste was somehow the primary sense? (No idea how that would work on a basically human frame -- a really long tongue is probably too much, but if they looked human right up until a twenty-foot tongue stuck out you could probably get a rise out of somebody.) What if they were entirely human, but entirely carnivorous? Make small changes, and then try to imagine how those changes would affect the cultures, individuals, and what it means about the environment they came from. Then play up those changes!

