I definitely agree. Shawshank Redemption is certainly not my favorite movie, but the fact that it reaches so many people, so many enjoy it, such a large number of demographics are moved by it, and how many of those people are willing to watch it repeatedly speaks to its power. I certainly think it's a more well-rounded, enjoyable, and powerful film than Titanic is, which is another ginormous crowd pleaser, but does that in a very different way.
One issue I do have with the episode is how Paul and Amy characterized the film as being like a warm embrace where nothing bad happens to the characters, how there are no real challenges. They did mention this in the podcast, but I think it should be emphasized that Andy Dufresne is RAPED. Repeatedly. It does not compute for me to have a main character, whether he actually is a murderer or not, be subjected to the most grievous violation a human being can experience and shrug that off as inconsequential. The rape is not graphic, exploitative, or depicted as a means of titillation. Instead it demonstrates the bifurcation of human extremes: how the lowest of the low can be overcome by the noblest of human endeavors, like art and the spirit within Andy. Obviously, rape in a prison movie is not unique to Shawshank, but that does not mean the film is an altogether easy experience, for the audience or the characters.