From Fairfax it will be 3-4 hours depending on traffic to Indian River inlet in DE or Ocean City MD but both offer good diving. Virginia Beach is another 3-4 hour away option. All of the above are colder Labrador current type diving, but 30-40 ft viz is common and I have had consistent luck diving there and the wreck are generally low relief with not a lot of tropicals (cold water, etc) but still nice and with spearfishing possibilities if you are into that.
The reality is that get-away traffic out of DC and NOVA basically sucks at all the times that matter to a diver, so it's 3 hours to anywhere near a beach.
Moorhead City NC is an excellent spot and is about 5-6 hours away. I get blown out there at least 1/3rd of the time and some times the viz can be the same fairly poor viz you get up north, at at times it is far worse, but when it is good it is epic with blue caribberan water, temps in the high 70's ato low 80's hundred plus foot viz, tons of tropicals, lots of sharks and a nice variety of wrecks. Epic.
Otherwise, it is 12-13 hours to North Florida for cave diving (but there are a lot of cave divers in the area who make the teop) You can also get fairly cheap flights to Ft. Lauderdale, etc to expand your diving opportunities. With a hotel close to the boat ramp, a good deal on an airline ticket and good hotel rates you can do a weekend in Ft Lauderdale for about the same as driving to NC for a weekend. Although when its good, the NC diving is much better.
Locally there are three quarries of note.
Millbrook is in Haymarket about 20-30 miuntes west on I-66. it is nie enough as quarries go but it is closed From now until late March or early April with the exception of a few chilly willy dives. It is also only open on weekends - except for a privileged few (instructors associated with The Dive Shop in Fairfax) which creates training problems for other shops and eliminates diving there as an option on the Monday and Friday flex days common to many peopel working in the area.
Dutch Springs is also nice, but cold and again falls in the 3 hours to anywhere geographic oddity category.
Guppy Gulch is a little closer but I've never been there.
Silver Lake Park in haymarket is supposed to be getting close to being opened for diving. It will hopefully allow year round diving as well as weekday diving. And perhpas scooter use (also not allowed at Millbrook.)
Finally there is Mt. Storm in WV. it is about 3,000 ft in elevation and is a 1200 acre cooling pond for a power plant so the temps are comparatively warm for the region. Roughly speaking it is near the base of the chunk of West Virginia that is sandwiched between VA and MD.
------
In terms of Dive Shops in NOVA, I prefer VA Scuba in Manassas and they are by far the most technically oriented. The Dive Shop in Fairfax runs in second place in terms of technical diving and is not a bad shop overall and they have a wide range of shop sponsored diving trips for both rec and tech diviers.
I like the management at Brass Anchor and they often co-sponsor some trips to NC, but it's a bit of a hike to get there on a regular basis from NOVA.
I also like Diver's Den in Baltimore. It's very down home freindly and they are the only Scubapro dealer in the area that I have any faith in. The drive can normally be done in about 75 minutes as it is near the beltway in Batimore and their beltway is a lot less congested than the parking lot ringing DC.