Answer

Your two questions contradict one another. In question A you assume that he is executed because of the severity of the act, while in question B you ask how this differs from a Jew. And that itself is the point: it is not so severe, and the proof is that a Jew is not executed for it. So why is a gentile executed? Because his life is worth less; it is easier to kill him. The Sages' view (which in my opinion is relevant only to the gentiles of their own time, as I have written more than once) is that there is no reason to preserve a gentile's life if he does not fulfill his basic obligations. In the case of a Jew, there is a chance that he will repent (and undo the prohibition by returning the stolen item), and therefore they do not execute him for every transgression. In other words, the difference is not in the severity of the transgression but in the severity of the punishment. The Sages held that killing a gentile is not so severe.
The Sages did not kill any gentile, and Aharon Shemesh argued that they did not kill any Jew either. He claimed that the laws of capital punishment were never actually practiced. These are laws that took shape after capital punishment was already no longer practiced in reality. I am not inclined to agree with that. They made principled determinations but did not implement them. Some would say that such determinations were never meant to be implemented, and it is easy to make them from the philosopher's armchair. If they had actually needed to implement them, their finger would have been less quick on the trigger. That may very well be true. It is like the Haredim today, who are very stringent about many things, counting on there being "gentiles" here to do the work for them (secular Jews and Religious Zionists). If the responsibility were on them, they would not be so stringent. For example, if there were many Haredi farmers, and certainly if everyone were Haredi, a sale permit would be found very easily. Just now Gafni and the rest of the gang were smearing Bennett over Sabbath desecration during the manhunt for the terrorists who escaped from prison. If there were a Haredi prime minister, he would do exactly the same thing, and rightly so.