A supposedly empty desert on the far side of the mountains has started growing. No one knows why. At the center of the desert lies a tall rock outcropping, hundreds of feet tall. Dust storms shroud the outcropping constantly, except for one night a year.
Saril had a dream. To open a library in the windswept wastes of Naarish, so that the people of the many villages and towns spread over the hundreds of leagues of desert could discover the joys of his books. For a whole year he kept his library open, but alas, almost no one came.
That is when Saril came up with his new idea. If people didn't travel to read his books, he would travel to them! Saril closed his library, hired a team of twelve camels, loaded up the beasts with all of his books and proceeded to invent the first nomadic library.
Now children and adults alike, looked forward to hearing the bells of Saril's camels as he entered their villages, as he tirelessly traversed the deserts in a long circuitous route, visiting every village and town he came across, in turn. It came to pas that Saril's traveling library came to some fame, and that is how the folk of Naarish became literate.
A word of warning though. Naarish has only six thousand volumes. He deals with those that lose or steal his tomes quite "harshly", by bypassing the town or village which was responsible for losing one of his books for that calendar year.
One of the camels in the caravan trips over a dark rock protruding from the sandy dunes. The poor animal has broken its leg and cannot continue. A cacaphony ensues as the animal suffers and the caravan train overseers complain passionately as they redistribute the animal's load across the caravan. (Let's just hope none of the PC's was riding this camel, shall we?)
As the camel is put out of its misery and the camel is skewered over a campfire - waste nothing! - someone takes a minute to inspect the root cause of all the trouble. To their surprise, the upturned rock is worked stone. Some frantic digging may excavate the bottom half of a gorgeously worked1 obelisk, and maybe even the small square forum below; but a more rigorous exploration of the surrounding dunes reveals a buried tomb doorway on each side of the forum.
A common mistake when writing adventures set in deserts is to assume that the climate is too ferociously hot to wear armor. Historically, most battles in deserts involved troops dressed in protective armor. Although they would have been miserable during the hottest part of the day or the hottest part of the year, desert weather isn't intolerably hot 24/7.
A legend tells of a people living deep in the desert, they appear at first as ordinary human beings, sometimes impersonating someone familiar to the PCs, before causing their features to disappear, leaving a blank, smooth sheet of skin where their face should be.
In ancient China, women bind their feet for cosmetic reasons, resulting in them not able to walk without help and walking in a shuffling gait.
Possibly this can be modified such that people do it for less stupid reasons.
Disclaimer: This is NOT a racist remark since I'm Chinese myself and hence entitled to freely judge Chinese customs. NOT sexist either since I'm female as well.