Check this out, I created it in Cinema 4D, havent used that software in years lol.
http://www.youtube.com/watch?v=OchFEGtle8s&feature=player_detailpage [^]
I apologise for the strange blurriness that seems to occur like a heartbeat, unsure why it is doing that.
Basically on the video the actual building is rotating, and it is sitting on top of invisible terrain I did that on purpose as the primary focus is the legs.
As you can see each leg rise and lowers in correlation to the terrain, whilst keep the building itself level.
I did not animate the feet, but if that can be done, great.