It should be noted that putting Helvetica after Arial in your stylesheet is self-defeating if your aim is to display Helvetica on Macs but Arial on Windows. Macs ship with Arial, so such declarations mean Helvetica will never be used.
Of the new fonts they recommend, I actually really like Calibri which is included in Vista, Office 2007 and Office 2008 for Mac.
I wouldn't rely on it solely as the safe assumption is only ~40% +/- 10 of your audience has it, but hopefully in time it will be a nice alternative. Not really a fan of Tahoma, too condensed for the screen in many cases.
Calibri is always described as a 'humanist' font, which I think makes it the kind of font you'd be pleased to take home to meet mother.
Aside from Lucida Grande and Palatino Linotype which everyone already knows about, this list is unbelievably unreliable... perhaps based on their limited sample it would work, but not for any major site that gets visited by other users than just designers.
Erm, the font-face property was originally a proprietary IE property and Microsoft have supported it since IE4, the snag being you need to convert fonts to OTF format to use them.
