Short Story:The High Meggas
On an alternate Earth in the High Meggas, millions of 'moves' across other alternate Earths, the loner Linsay is about to get some company: Anna Shea and Joshua Valienté. Only one of them isn't who they say they are, and a murderer to boot, so Linsay must figure out who is telling the truth and avoid the dangers of the High Meggas - the deadly consequences of the "Fists", and vicious, intelligent super-baboons.
The High Meggas was written around the same time as The Colour of Magic, and considered by Pratchett to be a great premise for a series of novels. He shelved that idea after the success of the Discworld, but revisited it much later as the foundation for the Long Earth novel series, with the aid of Stephen Baxter.
The story contains many elements that would later become more realised in The Long Earth, such as stepping, intelligent non-humans and disasters on alternate earths. While the later novels would re-use the names Linsay and Joshua Valienté from this story, the characters of the same names don't really match up: the Joshua of the novels is more like Linsay here, but younger and with a very different history. The stepping technology is also very different: the devices are belts, not boxes, and dependent on conventional batteries, which become a much-prized resource away from the original Earth.
The title of the story is slang used in both the story and the books: the "high meggas" are the alternate earths many thousands (or hundreds of thousands) of steps away from the original. Notably the short story does not use the terms "steps" or "stepping", but instead refers to "moves".