plus when you change providers, or move, you lose everything on the DVR!
Yup.
That's why the best possible solution - if you have a little money and time to spare - is to build a HTPC with a digital TV tuner. It gives you the best possible amount of space, the most options, and you can do whatever you want with your recordings (well, except redistribute them).
With a quad tuner, you can even watch and record up to 4 different channels at the same time.