In addition to the Hagstrom store, New York once had a thriving Rand McNally store, one of the original four along with San Francisco, Chicago and Washington. Long-time manager Edith Snizek was a legend in the business.
The Complete Traveler is now strictly antiquarian, where once they carried current guides and maps. So now the only travel publishing specialist shop in Manhattan will be Idlewild Books, but it is a small store focused on travel literature and experience, with very few maps. Longitude is a web store and does not have a storefont, but does accept walk-in visitors. They carry a good number of maps along with travel books.