The Threshold tool in Photoshop is under Image -> Adjustments (down the bottom)

The Render -> Clouds filter in Photoshop is too large, so I used GIMP to make one (I selected "Tileable" and filled it as a pattern, because I needed smaller details in a larger-res map)


A nice use for this method - increasing detail (the opposite of generalisation). So you have a low-res large-scale map, you can first apply the "Not-so-random" effect at that scale, then resize the image, blur a bit, and repeat. It can give you increasing levels of detail, much like the way real cartography works. It's not perfect, but it's close enough.