Mulberries--of the purple staining variety--
I had an 'orchard' of them in MN and they volunteered everywhere, including the chicken pen. I also inherited two large trees here with the house in UT--so I wouldn't say they are east-coast trees.
I can say that I do not get the hoards of mulberry seedlings in UT that I did in MN for which I am grateful. Still though, they propagate themselves very well.
Here, the birds do concentrate on the mulberries. That, along with cherry tree guard cats, allows cherries for me (if I can keep the western fruitflies from setting up their maggot nurseries).
Blueberries--sadly, I cannot keep them alive here because it is far too alkaline. I have a couple of 'honeyberries' (Lonicera caerulea) but so far I am not impressed and they really don't replace blueberries
