If you like the Costello/Frisell thing, there's also the live album they put out, Deep Dead Blue:
And also the "companion" album from Bacharach/Costello (no Frisell though), "Painted from Memory":
A couple of Frisell albums that never clicked with me were the Frisell/Holland/Jones set, and the "American Blood/Safety in Numbers" thing.