Tall fescue is going to be the most durable species, but as you and Scootr both noted, not the cheapest thing you can buy. I personally wouldn't bother with perennial rye, the regular heat and draught VA gets most summers will kill it, and you'll be re-planting the stuff every year.
A pasture mix that contains a majority fall fescue is going to be your cheapest bet for something really durable. These are cheaper than clean tall fescue seed, as pasture mix will contain other cheaper seed and even weeds, whereas pure mono-culture tall fescue seed has to guarantee a very low threshold of weeds. The idea in all of these (even the expensive 80/20 Tall Fescue / Annual Rye blends that are preferred for a new lawn) is that seeds like annual rye blast off in about 4 days, giving structure to hold, protect, and keep shaded the expensive tall fescue seed, which can take about 6 weeks to fully germinate. Pasture mix works the same, it's just not exclusively 20% annual rye with 80% tall fescue, it's a mix of many other grasses and weeds.
But you have missed planting season for this year. Planting season in southeast PA is mid-August to mid-September, any later than that and your tall fescue (the real money crop in the blend) won't have time to germinate before soil temps drop. I suspect you're a good week or two behind us in most of VA, maybe late August to late September, but either way, you're looking at next fall to plant. If you plant in the spring, you can get a beautiful lawn for a month or two, but most of it will die off in July without constant watering. Young grasses just don't have the structure to survive your typical heat and drought, without watering.