Crazy timing -- my wife and I were in the Grayson Highlands this past weekend as an anniversary celebration. Spent three days on the AT trails from Fox Creek down to Damascus, passing through the highlands, and it was awesome. The Highlands part is easily the most beautiful and enjoyable hiking I've done in VA.
For people looking for a similar (but smaller scale) hike, the Dolly Sods area of West Virginia has some of the same feel in places. Different in other ways. Both are incredibly beautiful and are my favorite two hiking areas within ~5 hours of Northern VA/DC area.