Yes, Lego is great! I know that, I went through this stage 35+ years ago. Also, coloring books are fine. And just playing outdoors, running and biking...

To learn programming, children have first to learn to read, write and compute. Unless you have a very gifted child, you will have to wait until he is 5 year old or so. Until then, all he will do is use the mouse, or using PLOKTA-mode with the keyboard.

On the other side, I have seen a friend's son, 6-year old. At school, he was learning to read and write, on his very first year. And at home, he was playing Sid Meyer's Civilization. According to his father, he was rather good at it.