We all love our Tivo or other PVRs (though my mother just got the Scientific Atlanta 8000HD which does HDTV but otherwise has a terrible UI. It's hard to imagine this was designed after people saw the Tivo or Replay.)
After you use your PVR, you get a large library. Deliberately recorded programs, or in the case of the Tivo "suggestion" mode, programs recorded at random that are similar to shows you have asked to record.
You can browse them like a directory. And once you use the PVR a lot you stop surfing the live TV by and large. So I suggest adding a "surf" mode for the recorded shows. Ie. pretend they are a set of channels that are on now. You would start surfing by seeing the first show live (but with the overlay showing what it is.) You could hit up or down and move to other recorded shows. For surfing purposes, the shows would pause and recontinue where you left off during this surfing session. After a while this would be forgotten for the next surfing session if you liked.
You can already browse through the descriptions, but this mode would give a more familiar feel to looking at the shows. This would be better for the suggestions than the requested shows. For example, I have often got many episodes of a show I watch, in order, and I don't want to browse them and spoil what's ahead. I don't even want to read the descriptions in many cases.
Oh yea, speaking of which, who isn't annoyed at the long delay for channel changes on PVRs, satellite boxes and digital cable boxes. Many of these have dual tuners, so why not do this: If the other tuner is available, start pre-buffering the "next" expected channel in a channel surf, so you can show it instantly. There is a downside to this, which is sometimes you will guess wrong or not have the other tuner and thus have to do the regular slow channel change, and I know that studies show that inconsistent response time is more confusing to users than consistently bad response time. But I think they could come to understand it. Of course, as tuners become cheaper, just have enough that you can always do it.