Start out with Tri-X, its what everyone starts out on. If you shoot film, and you have not shot a fair amount of Tri-x it is very odd. Practically everything is compared to tri-x in d76, its like a baseline for testing almost. Anyway its a classic and should at least be experienced before it is one day gone.
I also like tmax 400 as well, its very nice to use and enlarge. And I cannot disagree with the recommendations for HP5+ it is a very good performer as well. Every once in a while Ilford does promotion packs where you get 2for1 or buy 2 get 1 package deals of HP5+, that is a nice opportunity to buy it in bulk.
If you are in the US, try the arista premium from freestyle, it is tri-x, or atleast the last of it that Kodak is selling to them to repackage.