I am using a leadtek dtv1000t at the moment, picked it up from
http://www.arc.com.au for AU$53. It comes with a remote, but i don't think it is supported under linux mce yet.
As for foxtel, i dont have it but as darrenmason said the ozTiVo guide has data for it. The leadtek card has analogue (s video) inputs, dont know if it is possible to use both inputs at once, ie record FTA and watch foxtel ( or vice versa).
as an aside, Big W are selling usb bluetooth dongles for about AU$18, beats paying AU$65 for one

There seem to be a few aussies floating around here, please feel free to add any information you have (about suppliers, gear you use etc) to the wiki page.
http://wiki.linuxmce.org/index.php/Information_for_australian_users