Not sure if it's 100% Kosher, but Saul's in Berkeley makes a pretty good pastrami sandwich. I've never been to the east coast though so I'm probably comparing apples to oranges.
It was the only place open Christmas night a few years ago. The chicken in the pot with Matzah balls is another delicious entree there. Now I'm hungry.