Theres a small gun shop at the woodstock exit - go up 42 past walmart and the shop is on your right. They seem friendly every time I have been in there.
This site mentions a few of the other places that are somewhat neat -
http://www.virginiawind.com/virginia_travel/woodstock.asp
Ive eaten at the Spring House several times - but not while open carrying so I dont know how tolerant they are. Decent food and good service.
I think the fire tower is in national forest - and definitely some of the routes that link mention are as well. As such, I have no idea if the fire tower would qualify as a federal building, or if you can even legally carry hiking up to it. Obviously IANAL and the legality is for you to determine.
Also, the ride on 675 is worth it. Nice scenery. (George Washington national Forest). As you go out Rt 675 (Edinburg Gap Road, near the jeep dealership at the north side of Edinburg) you will find terrific spring water crossing the mountain. Just take EGR towards Kings Crossing. You will pass a small garage called Toms Garage just before you go up the mountain. On the downside of the mountain is the spring. It will be on your left hand side with a PVC pipe sticking out from the mountain. Best, coldest water to be found in that neck of the woods, bar none.
Maybe others can chime in?
Blade