The Sandmen are composed mainly of sand, as their name implies, and appear to be fully tan or white NPCs. They are typically seen in groups of four or five. When the player is spotted, they will become aggressive and engage in hand to hand combat.
Unfortunately, the Sandmen myth is false. It was included in a CLEO mod package titled Mythemix, and no eyewitness accounts can be found before the mod became prevalent.