I am guessing you are looking to set up Mythbuntu or Mythdora?
*Warning* : tv tuners in Linux require lots of setup. Vista already has great support for tv tuners in Vista Media Center. I have been using the ATI Theatre Pro PCI-E card for a while and can say it works well with VMC.
Check here for Linux friendly TV Tuners: http://www.mythtv.org/wiki/Tuner_Card#Cards_tested_with_MythTV
As far as a recording in the formats you mentioned, I believe my tuner records in .avi. You could always convert to the other formats, although I am not sure why it is necessary.