In Imperial China the quickest way to climb the social ladder would be to pass the imperial examinations and thus get some government post. However, this would not have been easy. Though the examinations were supposedly open to everyone, the exam questions required a deep knowledge of Confucian texts. Generally, only those from wealthy families could afford the education needed to do well on the exams. However, it was not unheard of for talented men of poor background to pass and get a government post. The famous Song dynasty poet and minister Ouyang Xiu passed the Jinshi exam (the highest-level exam) despite being from a poor family and being largely self-taught. However, he was helped a bit by the fact that his mother was literate and taught him how to read and write.

Though it's not so relevant to the question of what would be one's best chance to advance, among the ultimate examples of climbing the social ladder is Byzantine Emperor Basil I, who was born a peasant. He managed to become a servant to a relative of the then-emperor Michael III, whom he impressed with his his physical prowess and was hired by as a companion and ceremonial bodyguard. Basil convinced Michael III that his uncle Bardas was plotting against him and murdered him with Michael's approval. Michael had him fill Bardas's former position at court as Caesar and made him co-emperor. However, when Michael seemed to have begun favoring other courtiers over Basil not much more than a year later, Basil had him murdered as well and became sole Emperor.

So in this case I guess the answer is "get hired as a servant associated with the imperial court, make friends with the Emperor, and be clever and ruthless enough to usurp his position." Obviously not a path easily taken by the average person; Basil was both lucky and an extraordinary individual.

Two of your best avenues are entering the Church (which needs new blood regularly, and has pathways for advancement built in) and enlisting in service to someone with the capacity to reward you. But it's been pointed out that social mobility varied over time (not so much, 500 -1000; a great deal during and after the Black Death). And social mobility was a seesaw: you rise, a little or a lot; you get resources; your children are more likely to survive to adulthood. But when they do, you now have second and third sons whose position becomes increasingly shaky, and are at risk of downward mobility. Anecdotally, however, those are the folks most likely to be entrepreneurial: they know people and have some status and resources, and because they are at risk, they are motivated. So another answer to your question is, be a third son of the landed gentry, with good health, a good brain, and the medieval equivalent of a good Rolodex. Careers in service to a lord, in the military, or the Church would all be good options.

Or like I said, be alive during or after the plague years, and don't die. Then the field is wide open, even for a humble peasant, because labour is in short supply.

In the Ottoman Empire, being a slave in the Imperial Household was a good way to advance. Ibrahim Pasha was born a slave and became the power behind the throne, which was not unique. For most of their history, the janissaries were all slaves of the Sultan as well. For a long time, the Ottomans liked promoting slaves to positions of power because they lacked a center of support outside the Sultan and were thus thought to be loyal. Of course, palace intrigue and the power of these slaves resulted in a period of Ottoman history where the Sultans were little more than puppets of either their ostensible slaves or the Sultan's mother.

Ancient Korean empire of Chosun was very similar to China because it adopted the imperial examination system we called Gwa-go과거.

Basically, almost everyone would be entitled to it, with the exception being slaves, butchers, basketweavers, shamans and of course women. (Basketweavers were treated the same as butchers).

If you passed the examination three generations in a row, you'd be called a yang-ban caste, the nobility.

This was why many retired officials took up the job of teaching, called Hoonjang훈장 in a place (usually their own home) called Seoh-dang서당. Many laypeople then paid what they could to have their children learn the Chinese literature (as it was the official written language of the time, but not spoken, even long after Hangeul was made).

Almost every other folklore and fairytale of this period involves a young Seon-bi선비 (a learned person with yangban ancestry, current or otherwise) walking to Seoul (then called Hanyang한양) to take the examination. It's a core cliche for unexpected romance and adventure.

Or, you could take a similar examination in Martial training to become military officers. But this involved horseriding amongst others, so bot exactly something a layperson could do.

During the Sengoku jidai in Japan, military service would have been a clear (but dangerous!) method of social advancement. The nature of the era meant that daimyo and their samurai retainers were in need of manpower for their armies, and therefore, the bulk of those armies would have been made up of non-samurai "ashigaru" soldiers. In earlier eras, ashigaru would have been levied from the population directly, and while that system remained for most of the Sengoku jidai, what also emerged was a sort of semi-standing ashigaru culture (in certain regions of Japan, that is to say), with well-trained ashigaru "officers" who commanded well-equpped men in a professional manner, and who often remained in permanent or near-permanent service to the samurai. It was not unheard of for very succesful and lucky ashigaru to make the jump to being samurai themselves - indeed, the famous Toyotomi Hideyoshi, one of Japan's great "unifiers" (the other two being Oda Nobunaga, who came before Hideyoshi, and Tokugawa Ieyasu, who came afterwards), started off as an ashigaru. Distinguishing oneself in battle and impressing ones superiors (and, of course, being on good terms with those superiors) would allow several others to make the jump to being samurai. It was Hideyoshi, however, who would draw a clear line between who was and wasn't a samurai, essentially ending the social mobility that he benefited from, something that would continue into the Edo period (the period of rule by the Tokugawa shoguns). The Tokugawa bakufu was attracted to the idea of social stability, and enforced a rather rigid caste system. Nonetheless, the descendants of former ashigaru made up a significant portion of the samurai class in the Edo period, resulting in the samurai making up a surprisingly large portion of the population in certain parts of the nation (such as Satsuma and Chōshū, domains that would play a leading role in the Meiji Restoration).

Sources: Ashigaru 1467-1649 by Stephen Turnbull and A Modern History of Japan: From Tokugawa Times to the Present by Andrew Gordon.