I like September Ruby apple. It stores well and after 20-25 years my tree is still only 12 feet tall or so. It does have a habit to fruit heavily one year and not at all the next though.

Pembina is a reliable plum with sweet flesh and tart skin. Needs a pollinator though... Perfection plum makes a good pollinator with almost identical fruit.

Others will disagree, but I don't really recommend pears. I grow Ure and it is a nice tree with good fall colour and has small pears that taste just like a bartlett. But you need a pollinator, and what can anyone do with buckets of plums that ripen all at once? I eat maybe 10 each year and the rest just become a magnet for wasps and a mess on the lawn.

Grapes are an interesting fruit, though not a tree. Valiant is reliable, produces small clusters of grapes that taste just like Concord. Too seedy to eat many fresh, but they make fantastic juice and superb jelly. I know of one guy who doesn't actually eat any, just picks a big bowl of them each fall and brings them inside so he can marvel that he can grow grapes on the prairies.

A lot of Sea Buckthorn is grown up that way for its fruit. Hardiness not an issue, but the thorns are.