Heroes&Legacies (at the Arboretum Shopping Center) is indeed a nice shop. Fairly spacious store and a very nicely stocked walk-in. They even have a walk-in in their walk-in! A very plush, nicely furnished lounge (which is only for members, I believe), and a long covered outdoor porch (for us poor folk).
When you arrive at the Arboretum, look for Barnes&Noble and park close to it. Heroes&Legacies is on the second floor above it. It's not the cheapest cigar shop, but the selection and staff are worth the premium. Enjoy!