Over the air - Digital HDTV PVR any recommendations?

I also do not want to have to pay for a service like TIVO.

1)
HDHomeRun® Dual ATSC/QAM Digital TV Tuner works on a computer network. So you would have to connect a PC to your TV. Not too tough, but not nearly as easy as Tivo.

2)
I know you don’t want to build something, but just to show the options, here is an article on building a home theater PC (HTPC) with two tuner cards.
Ars Ultimate Home Theater PC Guide: 1080p HDMI Editio

Here is something promising. They just opened for business in LA.

What Sezmi offers is value, convenience, and personalization. For $5 per month (plus $300 for its hardware), you receive an indoor digital antenna (gussied up to look like a speaker) and a 1TB hard drive, capable of holding up to 1400 hours of programming.

The system receives local digital broadcast channels. And, if you upgrade to the $20 per month package, you also get a group of basic cable channels, transmitted over the unused bandwidth of its local broadcast channel partners.

http://www.sezmi.com/