I love Peabo Bryson's version of "Pretty Women." If I heard that version first, I would never have guessed it's from Sweeney or written by Sondheim. It's very authentic.
I love the Trotter Trio's entire album "The Fantasticks in Jazz." They've recorded a lot of Sondheim shows as a jazz albums (yes, "The Ballad of Sweeney Todd" as a piano jazz selection) but I just adore "The Fantasticks" album. It captures the melancholy, erhm, melodies so well.