EDIT: it occurs to me that I might be one of those "human-like skeptics" you mentioned, and quite frankly I'll own that. I'll defend my points as scientifically accurate, but for world building (with a suspension of disbelief and the nature of fiction writing) this may not be the answer you're looking for.
The short answer to your question is, not very similar at all.
See my answer on this question for a related topic: A mechanism for a level interstellar playing field
Generalized things that nearly all earthen species have (eyes, legs, a nervous system, ears, etc) are still incredibly specialized and therefore incredibly unlikely to evolve in another ecosystem. The solutions that earth organisms devised to environmental problems are far from the only solutions.
For example, nearly every complex organism on earth has eyes. And in many of the cases where an animal doesn't have eyes, it evolved from a creature that did. Think of the specialization there: we have an organ that is both a) sensitive enough to detect incredibly small variations in light waves and b) robust enough to survive direct contact with our outside environment. This organ translates these light waves into electrical impulses that our incredibly specialized brain is capable of understanding. Regardless of how good eyes are at allowing an organism to interact with their environment, the odds of another planet developing something that specialized in even a slightly similar way is ludicrously small. This same argument applies to almost any attribute of any complex organism.
But your question asks where we would likely be similar, and there are definitely some similarities we can count on; they just might not be the similarities you were picturing.
- Chemically, all earth organisms are based on carbon ("carbon-based lifeforms"). This is because, chemically, carbon is a very stable atom with four valence electrons, thus making it ideal for forming the backbone of complex molecules. It is reasonably likely that an alien lifeform would also be carbon based, though it is also possible that silicon based life may exist, as silicon shares carbon's four-valence bonding property. This means that we and the aliens would likely have certain chemical compatibilities with simple molecules.
- Biologically, we can fairly safely assume that any living organism must consume input (eat food) and must expel waste as a result. From this we can logically conclude that another organism would, at the base biological/instinctual level, seek out sources of sustenance and also release some form of unnaturally occurring byproduct in the form of complex organic molecules. In other words, its likely the aliens would have some form of hunting/farming/gathering system and a waste management system.
- Physically, aliens would need to be at the top of their planets food chain. Any species constantly under threat from a superior predator doesn't get very far in terms of social/technological development. What defines the top of the food chain will be specific to the ecosystem, but if we assume that the alien is also intelligent (like us) then it is logical to assume that their dominance of the food chain is due to their intelligence (strong creatures have no need to be clever, clever creatures have no need to be strong). Thus, we can assume that (relative to their home planet) they probably are not physically imposing, though they may very well appear as such to us.
- Evolutionarily, it is well accepted that all organisms on earth share a common ancestor (way, way, waayyy back there). In all likely hood, the same would hold true on an alien planet. This means that the aliens would likely share many traits with other organisms on their planet. On earth, an example would be eyes. Perhaps on an alien planet, most creatures have an array of heat sensing apparatuses.
- Socially, any species capable of advanced communication or interstellar travel must have a semi-stable social structure. While we can't assume that their society is democratic, or totalitarian, or anything that specific, we can assume that it is complex and organized.
The key point is that any truly alien species will not really appear similar to us in any readily noticeable way. Because of this (and the limitations of studio budgets) most aliens in sci-fi TV shows and movies adhere to the basic assumptions of legs, arms, eyes, ears, mouths, and oxygen breathing. On a related note, (if I remember the episode you're referencing correctly) I believe that line from Dr. Who is intended to poke fun at Dr. Who's tendency to fall into exactly this trap of assuming aliens are humanoid.
For more information on (what I think is a really fascinating and cool topic) check out this article from NASA on the Definition of Life.