I'm not sure I agree with your temporal notion of difficulty. One thing is not harder than another simply because the latter took less time to figure out. So what if many people have failed?* If someone with great insight like Ramanujan comes around and proves a bunch of new mathematical theorems, the fact that we now know those theorems does not imply that they are easier (or harder) to understand or make use of compared to some theorem which was not proved for another seventy years (there are examples here that go both ways.)

So why is robot.walk_to(...) "obviously harder to implement"? How could we know that simpler implementations will never be discovered? What you call "immense work" is not even a century's worth. In hundreds of years, making a robot walk convincingly might be no more difficult than implementing an effective chess AI.

I suppose I'm getting at a concept of minimality (like Komolgorov complexity). Just having a solution does not mean it's a minimal solution. We know enough to say perception is harder right now but not enough to say perception is intrinsically harder. We can't know that new breakthroughs (or just lots of gradual development) won't make these problems simple ones.

(*Actually, I do agree that lots of smart people failing at a problem is probably a good indicator that the problem is hard. This is still no guarantee though.)