Add a "dark sandstone" block that generates beneath regular sandstone.

Dark Sandstone would appear in layers between the current Sandstone block layers and proper stone (Granite, Andesite, Diorite, Stone, etc), but only in Beaches, Desert biomes, and Badlands beneath regular Sandstone and Red Sandstone.

Dark Sandstone color would be close to Mud Brick but more monotone and of a lighter pastel shade;  possibly something like #BB9977 in terms of hex coloring, or it can be a composite mosaic color between normal Sandstone and Red Sandstone, but a little darker or with more orange in it.

The addition of Dark Sandstone could help "push down" the depth of mundane stone layers so that the deepest Buried Treasure chests will keep within the Sandstone or Dark Sandstone layers instead of occasionally generating inside proper stone.

Dark Sandstone could also replace some of the regular Sandstone in the floor and walls of the fossae of Desert Temples (as Dark Sandstone and Dark Chiseled Sandstone). It could also replace the orange terracota in some Desert Temple instances to add a little variety to the structure.