When I was first getting started about 6 years ago with my
permaculture orchard/forest garden, I thought I'd have everything planted in the Fall of year 1. Fat chance!
I started off being very choosey, reading every book, and selecting all the varieties I wanted. Then, I went to
local nurseries, and they had none of these varieties. In the end, I found a hybrid approach better. Find the really good nursery growers who are in your region - the ones who have similar goals in their breeding programs to what you want from your fruit trees. Get their advice, and pick their best varieties. These may be ones that no one else has written about or heard of yet.
While I love the idea of growing from seed the majority of the time, then grafting if you get a 'spitter', I've got a small site, and in order to squeeze in all the diversity I can, I go with dwarf root stocks and grafted variety. If you can get seed from a variety known to grow well in your region and soil, that's a good way to go too - especially if you have a bit more
land to play with. It's different too if you have access to scionwood, and a bit of practice with grafting - then you can feel more confident hacking off the top of a tree and grafting onto it.
For apples, I read a bunch of
books on apples (The Book of Apples by Joan Morgan is especially awesome), and made sure to select older varieties that sounded really tasty and reliable, knowing that anything pre-1900 would be more pest-resistant. I was lucky
enough to find a nursery specializing in antique varieties, and they had all but one of the ten apples on my list.