Here's a first attempt at Virginia. Fairfax+Fairfax+Arlington+Alexandria is just over the right size for two districts, and everything else is small enough to "work". Of course, when I say "work", I include the caveat that there are two cases of using water contiguity (the 7th crosses the York, and the bridge across the James in the Hampton Roads district briefly goes through Suffolk), and the VRA is blatantly disregarded. I'm pretty sure a better map is possible, but (especially if you want to minimize water jumps) you're not going to do better than the current 2nd's -1016.
1: 1056
2: -1016
3: 215
4: -500
5: 1012
6: -1966
7: 517
8: 498
9: 427
10: -198
11: -47
It seems that if one really wants to stick to the rules, then Fairfax county can only be split between two districts. Since it is stuck with Arlington, Alexandria and Falls Church, that area is 9484 over the population. Technically at that exceeds 1% of a district and wouldn't qualify, but if evenly split each part should be over by 0.6% to 0.7%. If no other district is more than 0.3% under population the CDs can stay within a 1% range. That forces almost every other CD to be under population but not by more than 2000. With lots of counties and independent cities it turns out that it is possible.
CD 3 really is connected to Powhatan county in the west by more than a point (there is a small common border in the James river). Needless to say that not only are rivers hopped as needed but so is the Chesapeake Bay. If MD can do strange things with MD 3 along the Bay, then why not just hop it entirely in VA.
As I drew it, I used CD 4 to be the best BVAP district I could make given the constraints. It is 45.6% BVAP and 65.7% Obama. It is quite possible that it would elect a black candidate of choice despite falling under 50% BVAP.
Here are all the deviations:
CD 1: -1887
CD 2: -1993
CD 3: +724
CD 4: -1576
CD 5: -663
CD 6: -1862
CD 7: -1118
CD 8: +4923
CD 9: -373
CD 10: -738
CD 11: +4561