http://www.hardyfruittrees.ca/catalog/nut-tree
There are quite a few nuts trees that will grow in your area, walnut, butternut, buartnut, hazelnut, hickory and chestnut.
There is also pears and plums, sand cherry, and other
native fruits from the prunus sub-family.
There are
alot of berries too (raspberry, blackberry, strawberry, currant, gooseberry, jostaberry, atonia, elderberry, etc)
In general I don't like planting apples trees or others from the
rose family, that comes from Europe and isn't native to the Americas, they tend to need alot of spraying and such. That said there are quite a few zone4 apples. Have you gotten a chance to check out the regional fedco nursery? They have a nice selection.
https://www.fedcoseeds.com/trees/apples.
If the
apple trees are being killed by deer/etc, you might need to
fence them in right under the eaves of the house (I am only half kidding/lol).