They also have custom brain bits evolved to aid in this task

I was defining novelty somewhat more narrowly. The 'program' a child must learn concerns the coordination of its sensory-motor system. It has no prior experience of similar programs in the program-class Walking (ie., the internal sensory-motor actions needed to walk) . So we could call the problem of learning to walk a novel one for that child.

I'd be surprised if direct observation of parents etc. played much of a direct role in learning to walk. I would guess it more furnishes the child's imagination so it can simulate itself walking -- rather than the statistical AI approach of 'learning the distribution of walking patterns in visual sensation'.

The ability to simulate possible programs is one of the capacities which enable coping with novel circumstances. My guess is the child learns to walk by updating its simulation of what it needs to do in order to walk, by its attempts to walk.

This simulation<->sensory-motor-update loop is missing in LLMs, for example.

Some animals walk within minutes of being born. Of course on four legs it's probably easier.