Well, it appears that the answers are slow in coming here, so I'll lay out the basics.
Films (both B&W and colour) each have their own "personality", and, unlike digital photography, it's difficult to make changes after shooting and developing. Ultimately, then, this is going to become a matter of experimentation and personal taste, so whatever advice is offered here needs to be taken in context (the advisor's process and personal taste) and with a grain of salt. Use whatever you hear as a starting point, but remember to trust your own eyes.
Almost all film photography is going to involve the use of filters. With colour photography, that can be something as unobtrusive as a UV filter or a skylight (1A), neither of which has much effect on exposure. With B&W film, however, you are almost always going to be using something that blocks a significant portion of the light when shooting under natural light.
Almost all B&W films are much more sensitive to UV, blue and green (short wavelengths) than to orange and red (at least in comparison to the average person's subjective view of the world). We need to use filters to hold back the "excess" blue in order to get a "natural" representation of the scene before us. (The scare quotes are there because our eyes actually see things much as film does, but we compensate for it in the visual cortex.) Otherwise we end up with flat, almost-white skies with no clouds and everybody with blue eyes winds up looking like Zoë Wannamaker. And there's the problem of blemishes, which tend to be a bit on the reddish side, and come out considerably clearer than you'd like in an unfiltered B&W picture.†
That is going to have a large effect on the film you choose. The mildest, all-purpose outdoors filter in general use, the yellow K2 filter, eats a full stop of light (it has a filter factor of 2). So if you are using an ISO 100 film, using the filter means that you'd use the aperture and shutter settings you'd use on an ISO 50 film without the filter. If you find that a #25 filter (a fairly deep red that's labelled "light red") gives you a better rendition than a K2, well, you need to take its filter factor of 5 (2 1/3 stops) into account, so your ISO 100 film becomes the equivalent of an ISO 20 film.
Add to that the fact that for a lot of photographs, the "standard" contrast level (shooting at the ISO value and developing according to the basic instructions) is a little bit high. Many B&W photographers find that their "normal" is to overexpose by two thirds of a stop or so and underdevelop by a compensating amount to lower the contrast. That means that your ISO 100 film is actually more like an ISO 32 (K2) or ISO 12 (#25) film in actual use.
The obvious solution is to use a faster film. But with film, when you increase the sensitivity, you also increase the size of the grain. Current 400-speed B&W films are a lot finer-grained than the older ones were, but they are still much grainier than their 100-speed counterparts. That limits the size of the prints you can make before they become "artistic". If you are routinely printing larger than 8x10, you may find that a 35mm ISO 400 film is unacceptable (though the very same emulsion might be the darling of medium and large format photographers). On the other hand, if grain is your thing, you may find that you have to use the super-fast "surveillance speed" films -- actually ISO 400 to 1600, but designed to be "pushed" -- in order to get the grain you want.
There is another class of film I want to touch on briefly: chromogenic black and white film. These are films that one uses to shoot B&W pictures, but which are developed using the C-41 process and can be developed at your local minilab (if there is still such a thing). I'd give them a pass. The grain structure is the same as for colour print film -- it's composed of a bunch of amorphous dye clouds rather than grains of precipitated silver -- and that tends to look unsharp when enlarged. Like it or not, there's a certain expectation in viewers' eyes, and the grain structure of chromogenics don't meet that expectation. Then there's the problem of development -- home processing of C-41 is more difficult than ordinary B&W processing, and if you decide to let a lab do it, you need to deal with pro labs who understand push and pull (and charge pro lab prices) in order to get the contrast levels you want.
I realise that this is less an answer than it is a list of supplementary questions that you have to find answers to for yourself. Consider yourself lucky that you aren't being confronted by the vast number of options we had to face only a couple of decades ago. (Kodak, alone, had eight basic panchromatic emulsions, and there were both pro and amateur variants of most of them; then there was Fuji, Ilford and Agfa everywhere, along with innumerable smaller or Eastern European brands available at larger shops.) You will probably want to settle on two emulsions -- one ISO 100 and one ISO 400 -- to handle various lighting conditions, and learn how they work with both K2 and #25 filters (the K2 may not be strong enough under overcast conditions or in shade, and a #21 orange filter isn't usually enough of a difference).
No matter how you look at it, it's going to take some experimentation on your part to achieve what you want. Start by using a K2 and following the directions, and compare a couple of different readily-available emulsions at each speed. It won't take long to identify the film that comes closest to your ideal image. Then play with the amount of pull (it will probably be pull rather than push) it takes to get from "close" to "bang on" under normal lighting conditions. That gives you a baseline to work with, and you'll want to have a couple of different exposure/development recipes to handle flat overcast, etc., after you've gotten your baseline. (Adjusting paper contrast, by the way, only gets you so far, and it means storing more copious notes with your negs if you intend to reprint later.)
† When shooting under tungsten lights, the light source takes care of the red bias for you -- you can usually shoot women's and children's portraits pretty much unfiltered under tungsten and may even have to filter towards the blue end to keep men from looking a bit effete.