I understand that many churches were destroyed and even many priests arrested and executed, but how widespread was the violence across the entirety of the Soviet Union?
I don't think the height of persecution fell in the early period. I would point to mid-1930s instead, when the persecution could rely on the young generation that was bred since childhood into unyielding belief into the supreme righteousness of their supreme leader.
Nothing is more effective in extermination of undesirable religions as forcible installation of an alternative religion. Stalin, a former Seminary student, was able to pull this off by mid-1930s. Communism was presented essentially as a religion which one cannot doubt under the penalty of death. Just as Christianity often absorbed pagan rituals when it installed itself as the only religion in some of the new lands, Stalinism borrowed a fair amount of Orthodox Christianity. Th crosses were replaced with giant statues of Communist leaders, icons were replaced with the pictured of those leaders, mandatory in every official building and every school, etc. There were cases such as a 12-yo child sentenced to death for accidentally damaging a Stalin's picture hanging on the wall in his school.
Communism was showed little tolerance to other religions, but it did make minor allowances that would allow elder people worship whatever God they liked. However, the leaders of all the tolerated religions were required to report on their flock to NKVD, which could be the reason for the exceptions. Also, promoting religions was a felony. That is, if a grandpa would attend a church on Sundays he wouldn't suffer more than being blacklisted from any job promotions. However, if he would bring his grandson to the same church he would end up in Gulag. That led to church attendance quickly dwindling.
Most building that belonged to various religions were nationalized and used for other purposes. I recall that in Rostov-upon-Don, where I attended college, everybody knew where the Synagogue was, even though most people had no Jewish roots. The reason: the beautiful building of Rostov Synagogue was converted into a bar two generations ago, and was widely know and the prime place to have a beer or two.
The attitude to religion a) changed with time, and b) was different to different religions. In the beginning 1920-30-s, there was a militant anti-religious policy. Many churches were destroyed, or simply robbed and closed, many priests were prosecuted. Some were killed, others imprisoned or exiled. But the main religion (Russian orthodox) was never completely banned.
Other religions were banned/prohibited for political reasons. For example, the Greco-Catholic (Uniate) Church was prohibited after WWII. And only after the collapse of Soviet Union it was legalized again. The reason was political. In 1940-s and early 50-s there was a civil war in Western Ukraine. Greco-Catholic Church supported the insurgents who fought for the independence of Ukraine.
The attitude to Russian Orthodox Church changed dramatically during WWII. In 1941-42 Soviet Union government felt so insecure that they tried to mobilize everything which could help them to win the war. It is at that time the official ideology changed from "Proletarian Internationalism" to Russian nationalism.
And the church was enlisted. Since then it had almost official status within the state, though anti-religious propaganda never stopped. But after WWII the Orthodox Church officials were not prosecuted, I mean those who were loyal to the state.
During post-Stalin time, it was kind of "moderate persecution": it was possible to visit church briefly "to look into architecture and paintings", but practicing openly was not good for the job carrier. On the contrary, belonging to the Communist party was very good for the carrier, and this was of course fully incompatible. Membership in Komsomol was also incompatible. Most of younger people belonged to Komsomol, and being fired from there was not a good thing for a future.
Some low qualified worker would probably have no problems, but for an ambitious manager, or a student who wants to finish the education, leave alone seeks to become "something", it was really not an option to accept openly religion of any kind, not necessarily traditional one. Students like Jonas Trinkunas have been fired from university even for ancient pagan rituals. Reading science fiction was ok, but just fiction was already "not that good".
Apart from open demotions, Soviet agents were also instructing professors to make certain people to fail "objectively" various entry or graduation exams.
During Stalinism, belonging to religious group was an additional problem, but not belonging was not a protection. Owning property was more important and also sometimes even really truly hardcore stalinists like Nikolai Yezhow were executed by the system.