The first thing is that the uncanny valley is a moving target. People talk about "staying out of the uncanny valley", but the position of the uncanny valley depends on the person doing the viewing, and even then can change over time.
For example, my uncanny valley is far to the "left" of many people's. The deadeyed near-humans in modern video games are pretty far up my righthand slope, even though they seem to fall pretty clearly into the valley for many nongamers. On the other hand, Bayonetta is the creepiest thing ever made, wallowing in the uncanny valley even though she's obviously intended to be reasonably far up the lefthand side of that slope.
I don't think this is because of any intrinsic trait I have. I think the curve is a learned one. The hypothesis of the valley is that, by failing to be human enough, something sets off our creepy alert. I've spent enough time working with fictional 3D human beings that their attributes no longer trigger an alert. I think this can happen to everyone.
Therefore, I think the idea of "staying out of the valley" is actually a wrong-headed one. Attempting to climb the right side of the valley doesn't even have to work for it to work: just making the attempt and exposing the gaming population to these entities will cause their valleys, as a whole, to shift left. IE, the valley will always be located to the left of what we normally think of as humans, even if what we normally include in that group is a bunch of fictional characters.
This can also be seen in detail with people who collect dolls or similar. You go into someone's room and it's full of dolls, that's incredibly creepy. But they're used to it.
Of course, I'm talking about "to the left" and "uncanny valley" and all these other words, but there's an important thing to remember.
Not a Good Simplification
Despite the way we treat it, the uncanny valley is not a proven fact. It's not really even a scientific theory: it's barely a hypothesis. It's more of a simplification. It's easy to think of things in terms of the uncanny valley, but it's like thinking of planes as big metal birds: it doesn't actually explain what's going on and is absolutely no help in designing them.
My theory is actually the opposite. I don't believe that the uncanny valley is because we failed to be human enough. I think it's caused by the same thing that causes creepiness in any situation.
If you look at creepy characters and situations, the creepiness is usually caused by magnifying a particular attribute to the point where it is no longer reasonable. Sometimes this is straightforward, such as Freddie having a fire-scarred face and blade gloves: we take an attribute that is discomforting, and we amplify it.
Sometimes it can be a bit more abstract. Pyramid head's creepiness comes from the way we amplify inhuman characteristics. Not non-human, but inhuman: pyramid head gives off all the body language of a seriously disturbed person, amped to eleven. His namesake - the pyramid he has instead of a head - serves not to make him creepy, but to make him iconic. He is not creepy because he has a pyramid for a head, he's just easy to remember. His creepy traits are the ones he inherits and amplifies from the creepy people in our lives.
Approached from this standpoint, what we call the "uncanny valley" is clearly just what we call this sort of thing when we do it by accident. The dead-eyed characters from a modern video game aren't creepy because they just fail to be human, they're creepy because having pallid skin and flat, unfocused eyes is an unsettling attribute.
It may be true that they have to be fairly close to human for these attributes to matter. But that's not necessarily any reason to label it as a specifically "relative to human" thing. After all, there are plenty of creepy attributes out there, and even some attributes which are only creepy in certain situations. I can make a creepy cat in the same way I make a creepy person, but I'd probably amp different attributes. Moreover, what's creepy in one situation might be completely uncreepy in another.
For example, the new Street Fighter character C. Viper is extremely creepy to me. It's because she's wearing high heels. Obviously, someone wearing high heels isn't creepy in and of itself: it's the fact that a warrior in the Street Fighter universe is wearing high heels.
I also find cell-shaded Link disquieting. Not because he fails to be human, but because he fails to be a cartoon. He amplifies several cartoon traits and leaves others unamplified, creating a really uncomfortable result. To me.
So, in the end, I think that what we call the "uncanny valley" is simply when we accidentally amp up disquieting traits.