Yes, an HD recording played on an HD box on an SD TV will be displayed in letterboxed 16:9.
And from my experience, the picture will actually be somewhat better than the SD channels on the same SD TV. When I first got FiOS I got the DVR, which of course is HD, but I still had an SD TV. All worked fine, then I discovered I could watch all of the HD channels, and found wow, they looked better than their SD counterparts! Convinced me to go out and spend a bunch of money on an HD TV (this was over 4 years ago, prices sure have dropped since then!).