My wife and I have some good friends in the Pittsburgh (Squirrel Hill) area, and every time we go there we try to make it to either Primanti Brothers for a sandwich, or The Capital Grille for dinner.
There used to be a really good deli that was just up the street from Jerry's Records that was good also, but for the life of me I just can't remember the name right now.