Fortunately, there has been some scientific polling done on this topic, which is much more reliable than the TV poll where Stalin was voted the third-best Russian. Stalin still commands considerable respect in Russia and the Caucasus states, but attitudes vary greatly with the framing of the question.
In 1993, Stalin's raw favorable/unfavorables were at 27/55 for net -28 favorability. That's pretty low, but what if you ask if Stalin gets enough admiration for his role in building socialism? Then you get 42% of Russians in 1997 saying he deserves more admiration for building socialism, versus 30% who say he gets enough.
In 2012, the Carnegie Endowment and Levada Center polled Russian, Azerbaijanis, Armenians, and Georgians about Stalin. This study reveals that by far, Stalin is most admired for his role in WWII: 60% of Russians, 69% of Armenians, 72% of Azerbaijanis, and 76% of Georgians agree that "For all Stalin's mistakes and misdeeds, the most important thing is that under his leadership the Soviet people won the Great Patriotic War."
The two-mindedness of attitudes toward Stalin is on display in the following graph, which shows that pluralities in all four nations simultaneously view him as "a wise leader" and "a cruel, inhuman tyrant."
But lest we think that citizens of former Soviet nations are actually pining for Stalin, only 15% of Azerbaijanis, 18% of Russians, 22% of Armenians, and 24% of Georgians would "like to live in a country ruled by a person like Stalin." The study also finds that younger generations have "a growing indifference to Stalin."
Unsurprisingly, Georgians consistently have a better view of the most notorious Georgian than do the three other nations.
Sources: The first two polls can be found at the Polling the Nations repository. The full Carnegie Endowment study can be found here. There's a lot more in it; it's worth checking out.