What is the best software that could be used to teach some basics of programming to a smart 3-year old?
I really do not know if that age is suitable for learning programming. Smart is totally subjective.
At that age, some exercises could be logical, sequences. For example on the rabbit and the turtle story, what was first, the starting of the race or the rabbit is sleep? What is the consequences of that event? Logic is an important part of programming. He needs how to count first, how to read.
But Probably at that age is more important that he develops his motor skills, there are several parts, like gross and fine skills. https://en.wikipedia.org/wiki/Motor_skill
Give him a labyrinth where he can move around and follow a path with his finger. He will go to a lot of wrong turns, and one good efficient path.
Give him puzzles. Things to solve. There are some puzzles that need to have a sequence to be solved.
Give him an abacus, that could potentially show how to group, give him material to group by color, by size, shape, number.
If the above examples are too easy, try more complex variations on those. They are just to give an idea.
Programming is not a pure abstract skill, it needs logic, decisions, things that our brain can relate to. Do not skip that part of his cognitive process.
Sayed that. Take a look at this two sites:
The classic option would be Logo. There are numerous options, but the simplest might be a site such as Turtle Academy. Your child won't learn any transferable technical skills - not many careers requiring Logo skills, but aged 3, there is plenty of time to move up the technology ladder!
I agree with @Rafael that software may not yet be appropriate at such a young age.
An an alternative, I immediately thought of the board game RoboRally. In it, players move "robots" (tokens) around a board by "programming" the robots with a seqeunce of cards. In each turn, players prepare four or so cards and then their robot carries out the steps ("move forward", "turn left", "wait", "fire laser", etc.). Game play involves planning a sequence of events.
The fun part of the game is that the cards are "executed" round robin. Every player's first card takes effect, then every player's second card, etc. So the sequence of events you planned for may be foiled by the actions of your opponents.