Around 20 minutes into Happy People: A Year in the Taiga, Herzog's 2010 documentary about people living in a Siberian village, a WWII vet describes his experience of the end of the war. According to the subtitles he says, "And then Stalin came on the radio. His Russian wasn't too good."
This sounds like a stupid question but Stalin was Russian, right? Could this be just a different accent/dialect?
Stalin was ethnically Georgian. His first and native language was Georgian, while Russian was his second language. His Russian had a noticeable Georgian accent, but I don't think you could regard it as "bad" in the sense of him not being a proficient speaker--he was certainly proficient in Russian.
Stalin was born and grew up in Gori, which is about 75 km from the modern capital of Tbilisi. Georgia was, at the time, part of he Russian Empire, and he would have started learning Russian early in life. According to Montefiore (2007)'s Young Stalin, Stalin began learning Russian as a second language perhaps as early as second grade (so around 8 years old).
Stalin indeed was noted for his Georgian-accented Russian, as he was ethnically Georgian and grew up in Georgia. His initial writings were also exclusively Georgian, and he didn't switch to Russian until 1907, in part because his Georgian features made him stand out amongst the Bolsheviks, which while beneficial at times (it was a factor in him becoming the authority on nationality policy), he wanted to fit in more, and Russian would have a far wider audience than Georgian.
And for what it's worth, Stephen Kotkin's Stalin, Volume 1: Paradox of Power, 1878-1928 (2014) provides some information on the languages of Stalin, which I'll quote here (p. 10):
...Georgia was a diverse land and the future Stalin picked up colloquial Armenian. He also dabbled in Esperanto (the constructed internationalist language), studied but never mastered German (the native tongue of the left), and tackled Plato in Greek. Above all, he became fluent in the imperial language: Russian.
Now for some context on the above:
Armenians were the dominant people in Tbilisi, the capital of Georgia, and ran the business interests of the city, and of Georgia as a whole. As Stalin worked (albeit briefly) in a shoe factory (owned by Armenians, like nearly all factories), it is not surprising he picked that up.
Esperanto: This is the first I heard he knew any of that, but its not surprising, considering the purpose of the language (a common language for people) and its interactions with leftist movements.
German is expected, both because of the association with Marx, but also because Stalin lived in Vienna for some time, and dealt with German Marxists frequently.
There was a significant Greek minority in parts of Georgia, and while their numbers have decreased substantially since then, they still exist there today. Considering Stalin's frequent travels across Georgia and his mingling with the people in the country, and his reading habits (he would read hundreds of pages a day at times, especially history), again it is not unexpected.
Russian was obviously the language of governance and the Bolshevik movement as a whole. I don't think this needs to be explained.