Big Horse Creek, in NC also specializes in heirloom/antique apples. Cummins Nursery probably carries some older standard varieties in their offerings.
Starks and Miller always offer a few old-time selections, but I've not been overwhelmed with the trees I got from 'em 15 years or so ago.
I doubt you're gonna find good fruit trees - especially if you're not buying volume - one of this, one of that - for less than $25+ shipping.
If cost is a major concern, you could always buy rootstock and scionwood and graft your own.

I think they call themselves Virginia Vintage Apples and are very nice people with a very wide selection of heirlooms that thrive in VA.

lateriser, I'm just down the road in Nelson and highly recommend VVA. Once you subtract shipping, the extra $5 or so that you pay per tree will more than be made up for the advice they give you and the fact you know you're getting fresh, properly labeled, and healthy trees which will thrive in your area. When I planted my first trees in 2005, I went there and told them my goals and they picked 7 suitable varieties for me. In fact, if you go during the fall (weekdays when they aren't busy are good), you might be able to taste some of varieties before you buy. Last time I went, I expressed interest in buying a White Winter Pearmain and one of the owners said it was one of his favorites (of the 120 or so varieties they grow) and went and fished around his truck to find one for me to taste. You don't get that kind of experience through the mail/phone/internet.

You may already know this, but unless this heat breaks in the next few weeks, I'd wait until September to plant bareroot trees here anyway.

For the grapes, there is a guy here in Oregon who is a grape expert and sells grape cuttings. He's got both table grapes and wine grapes. Price is very reasonable and selection is enormous.

Grape cuttings are not hard to root.

Wouldn't you know, his name is on my other computer. I'll find the address and get back

The grape guy with the cuttings is Lon J Rombough and his web page is bunchgrapes dot com. He's in Aurora Oregon and does mail order.

As for heritage apples, I know where to buy them locally, but not where to get them mail order.

The heirlooms tend to be grown by hobbyists, not the big commercial orchards, which means they often don't have a web presence.

Wagonwheel sells heirlooms fairly reasonable, but it is on their time frame and they could care less about your schedule. They won't take orders at all in the summer. Fall orders only, and I think they custom graft what they have orders for.

I'm trying to order from them, haven't even gotten an order in, but one of their neighbors says they are legitimate and have beautiful trees, so I am going to persist.

Burnt Ridge has a few heirlooms, very reasonable price.

I would stay with the local source. If money is an issue, you might start with fewer than planned, then knock around the nursery toward the end of the season and see if you can make a deal. Get to know these folks and learn all you can from them. Misterbaby.

Lateriser:

I hate to waste money too, but don't mind spending some to get the best for certain things. Nursery stock is one of those things. You get pretty much what you pay for.

Agree with DJofnelson that is is very good fortune to have a source like Vintage Virginia nearby, which is run by very good, honest people, and where you can get good advice as well as good trees. Tom Burford, who has advised the nursery for years, is the acknowledged expert on ancient and modern apples in the state of Virginia. It just wouldn't make sense to bring in trees from the West coast or anyplace else when you have this resource nearby.

Having said that, I would caution you to be very careful when planting large numbers of heirloom apples. Many well-known heirloom English apples do not adapt well to the Virginia climate, and you have to know which is which. I planted a bunch years ago with visions of making English-style cider, but dropped that idea when I found I didn't need another full-scale hobby. Other heirlooms, while unique or unusual in flavor and appearance, are very shy bloomers and bearers compared with many of the modern apple varieties available today.

Lucky's suggestion of grafting your own might be the best if you want to plant lots of trees but hold down costs. You could plant out a bunch of rootstocks this fall, and be ready to graft in the spring. Scionwood is available for nearly all varieties, and I would be happy to supply you with some myself at no cost but mailing. I know you could handle grafting, since I have done it successfully myself, and many other beginners here have also been successful on the first attempts. You have all winter to study techniques.

Don Yellman, Great Falls, VA

That is truly great advice from Don and a generous offer. I agree that heirlooms have often gone out of style for a reason and Tom Burford is certainly an authority on which ones are worth growing in VA. Newer varieties tend to be grower friendly trees which means early and consistent cropping. They also tend to bear well in a wide range of conditions or they wouldn't be worth the price of the patent.

The owners of Vintage, and I wish I remembered their names because I've met them a couple of times and shared cider with the man (the fun kind of cider) at NAFEX meetings, are extremely nice and dedicated.

In their own orchard they grow a mix of new and old varieties which is what I suggest. Any apple you grow will taste much different than what's available in a store or even from a farm market and you are depriving yourself if you don't try growing a few of the new ones like Goldrush.

Charlotte at VVA has been very helpful to me in the past - and I've never purchased anything from them, and as Jellyman and Harvestman have indicated, having a knowledgeable 'local' source can be an incredible 'plus'.
I don't see how a small commercial nursery can even 'break even' selling a decent-quality 1-2 yr graftling at $25-$30.

Thanks for all the info guys. I really appreciate it. Don Yellman, thank you for the generous offer. I might have to take you up on that. I'm actually in college right now in the D.C. area, but when I get ready to go home for Thanksgiving break, I might contact you about the scionwood.

One option is to buy bench grafts and save some $s. Our orchard does benchgrafts at $9 a tree with a 7 tree minimum and no shipping charges with over 500 heirloom varieties to choose from. Many of my original trees came from Big Horse Creek Farm and Maple Valley Orchards both of which I highly recommend in addition to ours, Wagon Wheel Orchard. My kids and I start taking pre-orders in fall and ship out in March. I've just posted an updated list at wagonwheelorchard dot blogspot dot com. We love to trade scion wood as ours is a preservation orchard above all else. Good growing, Rick Godsil

Here is a link that might be useful: WWO Blog

there is also century farm orchards which is a great mail order provider of heirloom apples located in central NC. 90% of my trees are from him. he also sells a few of the most common modern varieties.
thomis