There are many options, including a NAS or even a computer that does little else than act as a server. I see you balked at $400, so while there may be some options, you likely will be limited. But, all is not lost as the Channels DVR does not require a huge amount of processing power.
Do you have any old computers (even laptops) that are just sitting in a closet?
Do you have any internal hard drives or external USB hard drives already?
Would you use storage for things other than the DVR, such as photos or other general storage?
Do you have interest in setting up a Plex server or anything that could make use of the additional capabilities?
The reason I ask these questions is that you can certainly get a NAS for the HDHR + Channels DVR setup. But, with a little advanced thought, a similar spend could get you many additional capabilities. In general, if you are going for a low-end pre-built NAS, with the big names being Synology, QNap, and Western Digital, you will have a great storage device, but not great processing power. Unless you are stepping up to $500-$1,000 units, you likely will be better off with a small computer and adding hard drives.
And remember, the HDHR + Channels software is going to set you back somewhere around $150 to begin with. That being said, if you are able to save $30-$50/mo on your cable expense, it will be very much worth it very quickly.