Companion to Helvetica Neue?

I'm looking for something that feels different but is still very legible and clean. I'd like to use the font for headers in a web interface. Any suggestions?

I realize this is a very subjective question with no one-right-answer.

Alternately, feel free to suggest other pairings with a font similar to Helvetica Neue. Ideally, free fonts... but mainly an elegant combo is what I'm looking for.