I personally favor a bit of state re-shuffling:
Join NoVA with central Maryland, DC, and bits of WVa to form the state of "Potomac".
Join the rest of West Virginia with 2-3 counties in western Maryland and some bits of western and southwestern Virginia to form the state of "Appalachia".
Join Delaware with the eastern shore parts of Maryland and Virginia to form the state of "Delmarva".
The rest of Virginia remains as "Virginia".
While you're re-shuffling states, join Idaho, Montana, Wyoming, and both the Dakotas all into one state, so that you finally have enough people to deserve two senators.
Excessive. Joining the Dakotas together makes sense; joining Montana and Wyoming together as well. However, I don't like having states that are too big, either population-wise or physical size. I'd rather break bigger states apart than have a handful of gigantic whales.
If you're going to do that, New York, Texas, California, and Florida should be split into 3 states each (or some bits merged into other states, or new states formed formed from multiple ones - ie turning Metro New York City into a single state). I'd also separate Chicagoland from the rest of Illinois, and Pennsylvania might merit two states.
