Mr. Beef, Al’s Beef, and Buona Beef are all very good. I have never tried Luke’s.
When you order, definitely order your sandwich wet (or dipped). You can have the giardinare on the side, in case you like it better without. I personally think that the best beefs do NOT have cheese on them. You should only be tasting the beef, garlic and spices. Cheese ruins the experience for me, this is an I-beef not a chesseburger or a cheesesteak we are talking about.
As for your other choices, Lou Malnati’s is good (I personally like Nancy’s and Giordano’s better but that is personal taste). Skip the Billy Goat though! This is one of my tourist pet peeves (along with Ed Debevics, and Michael Jordan’s restaurant when it existed).
Chicago’s best eating values and flavors are in its ethnic foods. Berghoff and Russian Tea Time are excellent as someone else pointed out. Greektown is the place I would really recommend hitting in town! Most of the places (Rodity’s, Athena’s, Greek Islands, Santorini’s) are great, and the prices are very reasonable. Nothing is better in the winter than a hot bowl of egg-lemon soup, some lamb, and a Metaxa to finish it off.