In your query sentence,
"While rock between two consistent strata might in one place be shale and in another sandstone, the fossils in that shale or sandstone were always the same,"
the description appears to involve a sandwich consisting of three layers — a top stratum or layer (let's call that A), a middle layer (B), and a bottom layer (C). Layers A and C are the 'consistent strata' — in other words, they are continuous, and their composition does not change.
The composition of the layer between A and C alternates between shale and sandstone as you move along the sandwich of strata, but the same fossils are found in this layer B, regardless of whether it happens to be composed of shale or sandstone at any given point.
NB — You will have noted that both shale and sandstone are a type of sedimentary rock, hence are formed in a broadly similar way.