A Landscape of a Stable
Talk to Mayno inside the Foothills Stable. He is staring at a painting and will then bring up that he just noticed there is a Shrine in this painting. This is the Shrine that the Shrine Quest is about.
The Shrine is the Tah Muhl Shrine and is actually visible if you stand at where Divine Beast Vah Ruta rests (after you have calmed it and defeated Waterblight Ganon). Look to the northwest and you will see the characteristic orange glow of a Shrine. You can pin it with your Sheikah Slate from this vantage point, making it easier to track down.
It is tucked inside a canyon in the Eldin region before it gets hot.