I like A&P Arms in Hampton. Knowledgeable folks and good prices (except Glocks 'cause they don't honor the LE/Military discount).
Nice perk is 5 free range trips (at Va Beach location) with purchase of a gun.
I haven't found any Hampton Roads store that fully honors the Glock discount. I went up to Town Police Supply in Richmond when I bought my 19.