Fresco Sans would work well, but if you’re leaning towards Univers I will assume that you would prefer a less humanist sans serif. Try FF Bau for a more expressive grot, or perhaps Galaxie Polaris from Village.

I’d look at OurType’s Parry Grotesque, even though it doesn’t have the G or K features you’re looking for.

Le Monde diplomatique uses Benton Sans and Arnhem, as far as i remember.
http://www.fontbureau.com/fonts/BentonSans/styles

Rich Hendel, for the Encyclopedia of North Carolina used Arnhem Blond for the text, and TheSans for much of the display. Worked quite well. Rich uses TheSans for a number of titles where he specifies Arnhem Blond for the text face; much depends on what kind of book it is, of course.

I’ll echo the recommendation for Benton Sans (or News Gothic), though I’ve always wished Benton had an italic.

There are a ton of great faces that would pair well with Arnhem, but it’s about finding the “chemistry” that works for your project.

There certainly are a lot of great faces for the task. Parry Grotesque is nice, I just can’t abide those curly drooping stroke endings for this project. Benton Sans is fantastic and is definitely in the running. Galaxie Polaris is a nice face but just doesn’t grab me for this project. TheSans is great in some aspects, like how the lowercase b is hoisting up its beer belly for the photoshoot. I just don’t like those inclined “M”s for some reason. I’ve always loved FF Bau, and it’s certainly a possibility, though it lacks the spring of something like Benton Sans, but makes up for it in character, like the eccentric Uncle of sanserifs, especially the bolder weights. News Gothic is too condensed in its natural state for my taste.

Anything out there like an FF Bau with a little more contemporary snap in its step, or a Benton Sans that listened to a touch more Tom Waits?

Thanks very much for your help.

Two that come to mind:
Proxima Nova
Brown Gothic

If FF Bau gets close, have a look at these Helvetica alternatives.