Here's the fourth animal-like robot I have built from Fay Rhodes' book "LEGO© MINDSTORMS NXT Robots Alive! Endangered Species": the Polar Bear.
You might have already seen Damien Kee's nice video on it; like him, I love particularly Fay's idea of making the front legs looking like they're walking.
Building time: around 90 minutes.
Programming time: 10 minutes.
Difficulty level for children: advanced.