Basically, I can understand the proofs' details for both inequalities, but still I have no idea why the bound of Hoeffding is sharper than that of Markov? Is there any underlying intuitive that can be explained in "natural language" other than mathematical formulas?
Hoeffding's inequality is proven by applying Markov's inequality (not to be confused with Chebeycheff's inequality!).
Hence it is NOT sharper but less sharp than what the Markov inequality can possibly give.
It is just simpler and more convenient to use which explains it's popularity. You can check that by reading the proof in the Wikipedia article of Hoeffding's inequality.