FM said:
But on the other, it's really really really hard to come up with anything truly alien, at least while still remaining in the realm of believeability. There's a reason most alien races in sci-fi are still humanoid (besides a lack of creativity) - that's what humans think of when they think "intelligent lifeform".
I'm afraid I must respectfully disagree.
I've seen a sci-fi setting where, besides humans, there were:
A race of giant (human-sized) cockroaches.
A race of beings with a tiny torso and eight long legs (with at most four touching the ground at any one time).
A race of one-armed rock-like beings. There's a stump, one eye, and an arm. That's it.
A race of beings composed of thousands of thin, interconnected strands (think tumbleweed).
The setting was made for table-top roleplaying, and so was fairly balanced. The humans were adaptable. The rocks were clumsy but hardy. The tumbleweeds were weak but agile. The cockroaches weren't as smart as the humans, but probably recovered from missing limbs more gracefully, and so on.
We can achieve balance without making every race human-like. The only reason several species in the Star Army setting are human-like is very simple: they're all descendants of humanity; they're divergent branches on the human evolutionary tree (although the evolution is mostly artificial in this case).
Plus, I'm quite proud of the fact that this is the only setting that I'm aware of that have tentacle monsters. :3