There are a whole lot of graphics cards + software that can do this, if you don't mind doing it on the PC.
If you want to do it on a standalone unit, try and find an old Series 1 Tivo, I believe they worked without the subscription service. The PC would probably be a better alternative though.
If you feel like tinkering with a DIY solution, there's
http://www.freevo.org, a Linux-based amateur project. No clue how good it is, but I've been thinking about trying it out.
I still think a regular Tivo is worth every penny though...
/Mike