There's no particular restriction on temple size by region population. As far as the expansion code is concerned, they're just guildhouses.
Shrines "motivate" followers in the region, increasing the likelihood of traveling to and conversions in nearby regions.
Priests can build shrines in any region that has more than a bare-minimum following (I think it's 5% or something?).
Yes, besides the obvious gold & time requirements, you need a bare-minimum following (10% or a fixed amount of followers to account for very small regions).
You will find the option under the religion tab.
