As to which lens, I would dismiss out-of-hand all the travel lenses. They just don't measure up. A good travel lens is a very mediocre lens. Why buy a quality camera and then hang a so-so lens off the front of it?
My own version of the poor man's holy trinity is: the Tokina 12-24 f/4 DX II; the Tamron 28-75 f/2.8; and the Nikon 70-300 f/4.5-5.6 VR. Together, these will run you a tad over $1500 new. There's no reason to buy them all at once, of course. But they will deliver the level of quality that the D5100 deserves. You might have lenses that appeal to you more for any of those ranges, but these three are all first-rate lenses at a very reasonable price. FWIW