Since OP hasn't stated what Playstation system in particular, I'm going to say Final Fantasy VIII. Especially for those who think games can't be magical, touching, immersive or narratively clever.
And on a more modern platform, The Talos Principle. Especially for those who think no first-person puzzler can match Portal at this point. Or for those who think videogames can't be genuinely daunting and thought-provoking.