Right firstly: Recording TV on a mac mini. This can easily be done using one of the usb DTV tuner thingies made by Miglia. My friend has one, you can use thier provided ariel or your own, and tune into all the freeview digital chanels, and record, or timed-record as much as you want (its all standard definition of course).
The Xbox plays HD content fine. However what videos, and how you play them is the complication. Firstyl, no DivX/Xvid here. IIRC its only .wmv and .mpg (mpeg 1 and 2 i think, defo not 4). Format support is going to be expanded to include H.264 and Mpeg4 come the update in may (officialy confired) which basicaly makes it as good as an AppleTV already.
If you're intending to play videos often, the only realistic way to do this is through Media Centre on XP or Vista. The xbox will stream videos off the aformentioned file types off your host computer. There is a way to get it to play friendly with macs apparently. That article has been posted on TUAW in the past week if you want it.
The mac mini will afford you ultimate flexibilty, by far. If you put VLC on it, it will play anything you throw at it. You wont have to faf about converting files, and will play stuff off usb hard drives and cd/dvd media fine (these are the main drawbacks of using 360 or AppleTV). As I've just explained it will record digital tv too, so really... it's a no brainer...
....not forgetting it as OSX and nifty remote too
