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.
Five men are herding fifteen horses down the road. They won't be very talkative, but are willing to sell a horse, or more horses if the heroes are interested. These men are horse thieves. They are already sought by regional militiamen. Anyone with a stolen horse (all are marked) may get into trouble. If found guilty, horse thieves face prison or even a hanging execution. Similar thefts have happened only a month before, and a reward is offered.