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).