A song that is a real grabber is Nature Boy. I don't know if it's strictly a blues, but it sure has a melancholy and blue feeling to it. I like this version by the late Abbey Lincoln, which has some great trumpet and sax (Roy Hargrove and Julien Lourau) on it too.
Along the same lines is Billy Strayhorn's Lush Life, although it's clearly not an easy song to sing well. The classic version of it is Johnny Hartman's with Trane, but surprisingly Donna Summer did an excellent version on her album "Donna Summer" that proved she wasn't just a disco diva. Quincy Jones produced it and it features some great musicians, including Ernie Watts on saxes. Check it out too for some ideas.