Thanks for the responses, Anixx!
If anyone has the time, could you post a video of somebody speaking Russian with a strong Caucasian accent? Not a parody, but a a real person...

And as for Stalin, if this accent is percieved very negatively, how was he able to gain people's respect, and become the leader? Doesn't it make him sound stupid or uneducated when he speaks? I mean many Russians (but certainly not all, I know!) have very high views of him, even today.