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?).
