If you’ve got the whole family, you don’t need anything else.
That’s the point of Helvetica and the International Style.

Bringhurst suggests Haas Clarendon, although I have never tried this.

If you want to be wacky, there’s Helserif. But a more important question is: what is the brochure about?

Thanks to all of you... I want to create a brochure for a real estate agency... I am using Helvetica neue and I would like to complement it with another one for the text within the brochure (long sentences). I tried using the same font everywhere (different variations though) but while I like the font for headers, logo letters and so on, I found it very cold and too... mechanic?... for long paragraphs of text. Was wondering if there was another font I could use to ease a little on legibility. Your suggestions are welcome.

Transitional and Modern Serifs should work quite well, 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 Transitional/Baroque 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, real estate.