The original problem was that backspace wasn't working in some programs when I ssh'd into my Debian box.
Matt, who's usually on top of all of this, suggested I check the "backspace sends delete" option in Terminal.app. But this not only didn't fix the problem (instead reversing the two sets of working/nonworking programs), it also makes it so I no longer have separate ^H and ^? keys.
After a lot of digging, I found that a terminal type of xterm (instead of xterm-color) made things work right, at the cost of color in my OS X terminals. Matt and I verified that either TERM setting works on his BSD box and on the Redhat UWCS* machines, so it's probably Debian's fault in some way. (Knowing Debian, they're probably following some standard and everyone else is violating it because that's what makes things work.) Rather than trying to change all of the Debian machines I use, I just copied the xterm terminfo over the xterm-color terminfo in OS X. (If you're looking to do this, it's in /usr/share/terminfo/78.)
The other problem I was having was my UTF-8 mutt was all corrupted. It turned out to be a simple setting: the "Wide glyphs for Japanese/Chinese/etc." option in Terminal.app was also making the Unicode line-drawing characters double width. This, coupled with it wrapping the extra-long lines, means that the lines following these doublewidth characters were indented, which corrupted the next line, and so on.
The final thing that was driving me nuts was happily fixable: I made pgup/pgdn send those keys and fn-pgup and fn-pgdn into the terminal scrollback, like I'm used to elsewhere.
* UWCS = University of Washington Computer Science.