I learned that 氏 is more respectful, and have seen it used with presidents and prime ministers, but I am not sure if it is still appropriate to use both terms when addressing people verbally.
The sound of 「氏」 is highly objective, compared to 「さん」. On the other hand, 「さん」 is still respectful but also often includes somewhat friendly and subjective nuance.
As a result, it is very common to say 「○○さん」 to mean "you", while it is not standard to say 「○○氏」.
In contrast, 「氏」 is preferred to 「さん」 in news articles, as it should be written in an objective style.
So, the reason you see 「氏」 is used for presidents and prime ministers is that they often appear in such formal and objective writings as news articles. In our daily conversation we often refer to the prime minister of Japan by 「安倍さん」 rather than 「安倍氏」. This is because spoken words tend to be more or less subjective.
The difference of the two words are rather their nuance. There is no restriction to the kind of people to which 「氏」 and 「さん」 can be used.