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.