You might be able to use the 4:3 Smart-screen option as well. Your TiVo will then include a signal (in the VBI with CC info, I believe) that indicates that the video is anamorphic. Some 4:3 TVs can detect that signal and automatically letterbox the video by squeezing the scanlines closer together (no image data is lost).
Some DVD recorders can also recognize this signal and mark the recorded video as anamorphic as well, so you can play the recorded DVD back on a standard set and have it letterboxed like a store-bought DVD would. Check to see if your recorder supports this. Even if it doesn't, the video will still be recorded stretched so it can be displayed anamorphic.