So that's why there weren't any in my large world...
Imagine my surprise when I gave up and opened a map viewer and found no shrines. However, I did search for the shrine tile to make sure, and I actually did find a single sword shrine - just the sword in the stone. Far underground, near the ocean. And it dropped a Terragrim, to boot. Just not what I was looking for...