The Stanley Prune Plum is the quintessential plum variety for prunes (according to my mom, anyway). They do make great prunes, and they do taste excellent fresh (the best plum I've tried fresh, actually, but I haven't tried loads of varieties—just a few). They're fairly cold hardy, but our two semi-dwarf trees that we had (at separate times) seemed to have been prone to diseases when they got old (although they still seem to produce when diseased, as long as it doesn't kill them—fruit appearance may be impacted, however). The trees maybe lasted about ten years each, before getting diseased, I'm guessing. By the way it feels when I eat it, this variety seems to be very nutritious. They're substantial. The flesh is firm and not watery. You definitely need to chew it (even when fresh). They don't split or break easily. In my area, they are tart when first ripe, but gradually get sweeter (although they still maintain some acidity when sweet). Size is decent. They're not tiny like some plums (maybe a couple inches long, and over an inch wide). They have purple skin, and are not purple inside. They look kind of dark red when canned, interestingly, though (they're pretty nice canned, too).
This is a very productive variety (at least in my area, which is to say, southwestern Idaho, in the USA—the USDA hardiness zone is about 4-6, depending on the year, but usually -10° F. is about as cold as it gets; the record is about -25° F. or maybe a bit colder). You should get lots of plums on one tree.
We never had a problem with Stanley plums losing fruit to frost. We did have problems with apricots, apples and cherries losing fruit to frost, however. Perhaps the rootstock helped our trees, though.
We only had one plum tree at a time; so, I can vouch for the self-fertile quality of Stanley. We did have other trees in the Prunus genus, however (apricots, peaches, cherries, sour cherries, plumcots, and nectarines), which can potentially cross with them (and hence might pollinate to some degree). However, I don't think it was in bloom at the same time as any of them, except maybe the peaches and nectarines (which weren't there for our first plum tree; all we had on the property with the first tree was an apricot, which bloomed far too early, and on some years, some young cherry trees, which died). I think it avoided the frost damage by blooming a little later, but the blossoms were definitely more durable than apricot blossoms.
Our area is not humid; so, I'm not sure how these do in humid areas.
I have not tried the Damson plums suggested by Rincewind42, but they sound interesting.