Obviously provincial is the adjective to describe a province, and parochial is the adjective to describe a parish.
I've gone through a number of definitions, and although the words are similar, and can in fact both be used in certain cases, there's one connotation that's nearly always mentioned in definitions of provincial and that is always absent from parochial.
Before I get to that though, what they have in common is that they both describe things that may be confined, stringent, or self-centered in their outlook, practices or beliefs etc.
The one feature that always distinguishes them in definitions is that provincial can be used to mean things like unsophisticated, simple, rustic, unfashionable, lacking polish or urban refinement and so on. This is clearly as a result of provincial having to do with the "provinces", which often have the meaning of areas rural or outside urban centers or cities, and all the attendant perceptions or stereotypes that come with people living in the "provinces".
These ideas of lack of sophistication or urbanity or gracefulness or social refinement or good tastes are associations more common to "provincial", and rarely or never associated with "parochial". This seems to make sense because parochial has a religious background. Of course you may say that parishes nowadays don't always have to be related to religion, such as the administrative parishes in many parts of the world. In some places there's a distinction between a civil parish and an ecclesiastical parish, where parishes may just be similar to names like counties, districts, regions etc. But the history of parish is quite closely linked to diocese, whereas the province isn't.
So here are the parts of the definition that describe this particular connotation. Pay attention to words used repeatedly, such as unfashionable, unsophisticated, rustic and simple.
3b : a person lacking urban polish or refinement
2.Of or characteristic of people from the provinces; not fashionable or sophisticated:
American Heritage Dictionary
3.(Sociology) having attitudes and opinions supposedly common to people living in the provinces; rustic or unsophisticated; limited
3.rustic, narrow, or illiberal; unsophisticated; parochial.
Random House Kernerman Webster's College Dictionary
2.Of or concerning the regions outside the capital city of a country, especially when regarded as unsophisticated or narrow-minded.
Oxford Living Dictionaries
having opinions and ideas that are old-fashioned and simple
3.old-fashioned and not interested in anything new or different – used to show disapproval
Longman Dictionary of Contemporary
2.old-fashioned and conservative, especially because of not living in the capital city or a large city
These words are nowhere to be found in the definitions of parochial (you can check for yourself if you like). They do share other descriptive terms though, such as limited, restricted, confined, self-interested and narrow. However you won't find the other words I mentioned up higher. Also, I don't remember seeing the word "conservative" in any definition of parochial but did see it in one for provincial. Also remember I didn't check all dictionaries, I checked eight. And I may have made an error or omission along the way.
I personally feel that provincial connotes "stupidity and lack of intelligence," while parochial connotes "(culturally) conservativeness."
I think your idea about provincial is partially right, we can debate about stupid or simple or unsophisticated. Parochial meaning "conservative", although I never saw the word "conservative" used in any definitions, you may reasonably have that view, I suppose, as they both mean centered upon their own ways or confined to their own beliefs, and to the extent that one's ways may be tradition-based, then it's possible.
What is the subtle difference between the two?
As I mentioned, the meanings can overlap, whether the unsophisticated/old-fashioned meaning is meant or restricted/confined in beliefs meaning, it'll have to be figured out from whatever the passage is. Often this isn't always possible, but the same goes for many terms and words.