I downloaded that Mario Christmas one a bit back and... it's okay. As for "traditional" Christmas songs, I'm a little shocked to now realize I don't have any favorites. I mean, there's songs I'll listen to if they're already playing on the radio, and songs I unconsciously whistle while trimming the tree, etc., but not really anything I'd seek out.
On a somewhat related topic, I wrote--and have continued modifying--a "Christmas song" (only because it's to the tune of "Hark, the Herald Angels Sing") a few years back. I will not, however, post it, as it is a collaboration, a la one of those "We Didn't Start the Fire" parodies, encompassing all of my friends' and my (oft-crude) in-jokes. I would be more worried if you understood any of it than if you didn't.