Phoenix is a large genus of feather palms from throughout milder regions of the old world. It includes the date palm, P. dactylifera, and indeed the word Phoenix is the Latin word for "palm". There are many species, some of which are quite variable, and to categorize them is a challenge to taxonomists and hobbyists alike. To complicate matters further, they hybridise freely with each other, and plants from nurseries might not always be true to name. But here is an overview of the species that show some cold-hardiness.
P. canariensis is one of California's most familiar feather palms, and is often tried in the Pacific Northwest. It certainly grows well in a cool-summer climate, but it has a pretty well known hardiness limit around -9°C/16°F (frond damage occurs around -6°C/21°F), and therefore it always gets knocked out if left unprotected through a severe Arctic blast. The northernmost known large, unprotected P. canariensis in the Pacific Northwest is in Gold Beach, Oregon. There are some truly monstrous specimens to be found in the Brookings area.
P. dactylifera, the date palm, is often compared to P. canariensis, but it is definitely at least a little hardier in dry climates, and, it is said, in southern Europe. So far its performance in the Pacific Northwest has not been all that exciting, however. Since it is so variable, it is always worth trying plants from different seed sources. P. theophrastii, from Turkey and Crete, may be just a bit hardier still, but it is a smaller and rather bristly looking palm. Turkey is also home to an unnamed species referred to as 'Golkoy-Burdun', which is probably even hardier than P. theophrastii and grows in swamps, but is very rare in cultivation.
Possibly the most intriguing Phoenix is P. atlantica from Morocco and the Cape Verde Islands. Plants from the Cape Verde Islands may not be especially hardy, but the Moroccan form grows up to 6,200' in the Atlas Mountains which suggests more hardiness than any other Phoenix species. It is generally considered to be very similar to P. dactylifera and may not be given distinct status as a species. However it does have shorter, stiffer fronds and branches dichotomously in its upper parts! There are also some Phoenix palms near Elche, Spain. It is not known whether they are native and should be given the name P. iberica, or whether they were introduced millenia ago and should be considered a form of P. dactylifera. In any case it would be worth trying one. There is also supposedly a palm from Southern Spain called P. chevalieri.
Then there are a number of Asian Phoenix species that are somewhat hardy. These are less well known so it is hard to say exactly which are the best speices to try. One nurseryman believes that the hardiest species are P. humilis var. humilis and P. hanceana, both of these being a little hardier than P. canariensis. Certainly P. acaulis, a diminutive species, must be somewhat hardy, since it grows at fairly high elevations in the Himalayan foothills. Also from the Himalayan foothills is P. rupicola, which looks much less bristly than other Phoenix species and in fact somewhat resembles a coconut - but it is probably one of the more tender species from this area. P. sylvestris is found throughout India and is probably a little less hardy than P. canariensis, but often hybridised with P. canariensis to produce a palm that is more vigorous and recovers from cold more quickly. This hybrid has been very successful in the Southeast US. There is also P. loureiri, a form of P. humilis native to the Himalayan foothills over towards Thailand, and P. taiwaniana from Taiwan. I have also heard of something called P. inchuii (inchuixii?) from Yunnan China, but can't comment on whether such a plant really exists or what it looks like (though we do grow many hardy plants from this region). I suspect that many of these palms would probably not grow north of Curry County, Oregon, but they remain largely untried. And there is also a single-trunked palm called P. andamanensis, which I know nothing about, and P. macrocarpa which may be a hybrid.
Finally, P. paludosa, P. pulsilla, P. reclinata, P. roebelenii, and P. zeylanica can tolerate a little frost but are probably altogether too tender for our region. Although, if one were to collect seed from P. reclinata at the coldest part of its range in South Africa, it might result in a somewhat hardy palm. And P. roebelenii is perhaps small enough to fit into a sheltered entryway in Brookings.
I am not going to attempt to specifically rank the hardiness of Phoenix species beyond my general comments. All species are fairly drought tolerant and might show somewhat better hardiness if planted in a very rocky or gritty soil. They are also all capable of making good growth without a lot of heat, even the tropical species. I would resist the urge to plant P. canariensis unless you have an exceptionally sheltered spot for it and can offer it some protection (although, it is fun to grow). It would be fun to try desert species P. dactylifera, P. theophrastii and P. atlantica in the very mildest places east of the Cascades, but I would still consider this to be a huge risk at best.
Phoenix palms are always very easy to grow from seed, with a little bottom heat. You can save the seed from store-bought dates and plant them.