Because I was asked this several times in the last months and today this question also appeared on typophile, here are my suggestions (further ideas welcome):
Transitional and Modern Serifs should work quite well with Helvetica, but also Garaldes like Garamond – depends on what kind of atmosphere you aim at. If you are looking for a more human, legible, friendly touch, choose an open typeface from the Garalde subclass like Plantin, Galliard, Swift or Proforma. For more neutrality browse the Transitionals/Baroques like Utopia, Rotation, Farnham. More classy, austere? look in the areas of Modern (bracketed) typefaces.
good suggestions: http://www.fontshop.com/fontlist/subclasses/
http://www.fontshop.com/fontlist/alternatives/times_new_roman/
I would recommend a rather broad face with not too much contrast, something sturdy.
Stabil!
Update 2010: FontShop.com publishes a greatly illustrated article with my suggestions
__________________________
Im Prinzip ist die Helvetica mit fast allem gut mischbar. So erträgt man sie auch viel leichter, da man zu einem etwas langweiligen Klassiker unter Umständen auch mal was gewagteres kombinieren kann, ohne dass es im Ganzen total abgedreht aussieht.
An Serifenschriften passen sowohl dynamische (Renaissance-Antiqua) als auch statische (Klassizistische Antiqua), finde ich, wobei letztere aber oft nicht so gut lesbar sind. Vielleicht in der Mitte suchen, Barockschriften erfahren ja eh gerade wieder eine total Renaissance.
Ich mag z.B. gerne Celeste von Chris Burke, oder Fairfield, oder Ehrhardt. Ein Klassiker zur Helvetica ist auch die Concorde von GGL (so wie Utopia von Frutiger zur Univers).
Oder ich könnte mir auch eine mit etwas kräftigeren oder geraden Serifen vorstellen, z.B. Candida oder Stefan Hattenbachs Delicato, die ist ähnlich der Enigma (beide aber schon recht eigenwillig). Robuste Serifen wirken jedoch eher informell, weniger elegant.
Die Frage ist also immer, in welche Richtung man das neutrale Arbeitstier treiben will – eher freundlich oder eher streng? = eher dynamisch oder eher statisch.