Type was a passion for me as a young designer, so I feel obligated to chime in. I'll call them all by what I consider the original name; close copies are often available under other names.
Frutiger has worn extremely well for me. I've been a fan of it for over a quarter century now, and it's my "house font" for projects that don't have other considerations. Because it was originally designed for signage at Paris's Charles de Gaulle airport, I think it reads well at extremely tiny sizes. Stone Sans also works well that way, and Meta is a fresh, sort of European looking, alternative for high legibility. Ocean is a personal favorite that has a distinctive character, especially the italic. Gill Sans is a curious paradox, a face that has a small x-height yet is still quite readable at tiny sizes, but I associate it strongly with Great Britain. Trade Gothic, News Gothic, and Futura carry specific connotations to me of postwar modernism, but if done skillfully they can give maps a distinctive look. I've been using Myriad a lot lately, often as a combination with Minion, precisely because they call so little attention to themselves. All the NACIS conference materials, for instance, used those two faces.
In recent years, I've tended toward condensed faces on street maps, and Frutiger and Univers, both designed by Adrian Frutiger, are handsome and well-designed choices. My main objection to Helvetica, besides extreme overuse, is that it was not designed as a family. The black or condensed versions are too unrelated to the regular weight. Also, Helvetica looks best when tightly letterspaced, which is not the way you want to set 5 pt type on a map. In contrast, a map done with eight different weights and widths of Univers will hang together as a well-designed ensemble. You can set the road names in light, landmarks in medium, and the placenames in black to set up a nice visual hierarchy.
For serif fonts, the biggest problem is x-height and slender strokes. That's a problem for all but the most modern Baskervilles, Bodonis, Garamonds or Caslons. I tend to think of Times as both overused and underweight (it was designed for letterpress newsprint reproduction where it would fatten up a lot on press). Sabon and Plantin have x-heights that are too short for my tastes. I consider Palatino to have the most beautiful italics, but the roman sets a bit wide for my taste. For some years I liked Trump Medieval, but it's rather idiosyncratic and sometimes calls too much attention to itself. These days I like Veljovic or Utopia (and the aforementioned Minion) as good workaday serif fonts.
I think of Hermann Zapf's Optima as being in between serif and sans-serif. Since I recoil at the thought of mixing sans-serif faces (and am not very keen on mixing similar serif faces), I find it very useful for book projects when I have no idea what text or caption faces will eventually be chosen.
A new challenge for me has been fonts for use on web maps, where at small sizes only a few pixels have to communicate the character shape. So I've experimented with the fonts, such as Verdana, that web browsers introduced, figuring they had been optimized for readablity in pixels rather than ink.