Cross pollination is probably the main issue indeed. Also, with the very odd spring weather we had this year, even if your tree had been more fertile this year than previous years, without sufficient bees or other insects to pollenize, this could have had a big impact. Did you see many flowers this year? Any late freezes could have also killed a lot of blossoms. Lots of possible problems this year (depending of course on your local climate/weather).

My point about the bees is that they seem to wait in spring until they are very sure the weather is okay before they come out of their hiding places. Since we had a warm March but a cold April in 2012, the apple trees began to bloom early in late April-ish, however due to cold temperatures in April the bees were not buzzing around yet to pollenize -- the bees waited until warmer times in May or June to come out of hiding since April was relatively cold. So even if you had a lot of blossoms, if the bugs were still hiding due to cold temperatures, those blossoms would not have produced many apples, and I think that is what you are seeing, in combination possibly with the late freezes which also occurred in April and May that could kill blossoms.

As for a good pollination partner for your Honeycrisp, I cannot speak highly enough of my favorite apples, Cortland and Jonamac. Both varieties have McIntosh as parents and have very similar qualities, and both are good for growing in zone 4. They will bloom a few days earlier than Honeycrisp but there should be enough overlap to pollinate. They are excellent all-purpose apples. They are delicious fresh, but in my opinion they are the absolute best apples in the world for making sauce and pies. They might not hold up well for canning though, as these are soft apples that do not last long in storage -- sort of the opposite of Honeycrisp that is firm enough to hold its shape virtually forever. One word of caution (or not!?) is that I know Cortland is a tip-bearing apple, which means that if you prune it at all, you need to be careful because most of the flowers and fruits will occur at the tips of the branches. So if you prune heavily, you could lose all your flower buds and fruits for the following season! And I don't know but I have a feeling that Jonamac is the same way. But if you're not very interested in pruning, then these are good trees to have as they will produce nicely each year.

If canning and keeping is important to you at all, then instead of Cortland and Jonamac, I might look into the relatives of Golden Delicious such as Grimes Golden or Sinta, which are superior to Golden Delicious in flavor but a little harder to find in nurseries (although I think Maple Valley Orchards has them). I believe these are also good in zone 4 (considering that's where Maple Valley is!).

It would be best to plant a new tree in spring, May 1 or thereabouts. But go ahead and order the tree earlier than that for a spring arrival to ensure you can obtain the variety and rootstock (i.e., dwarf, semi-dwarf, full size) that you prefer.

Best of luck to you! And don't worry about not pruning your Honeycrisp so far. You'll probably want to prune it more as it comes into full bearing, but until then you should be okay not to prune it much at all. Be careful though if you do get a Cortland -- you can lose a lot of fruit if you prune it too much -- I know this from personal experience!

Crabapple trees are indeed good pollinators; however, Chestnut Crab and Honeycrisp share Malinda as a parent or grandparent variety, so the Chestnut and Honeycrisp *might* not pollinate each other very well as it would be incestuous. I'm not saying that it won't work, but you should take the fact into consideration -- what I am trying to say is that typically you would not want to pair, for example, Jonathan with Jonamac, and Honeycrisp and Chestnut is much the same way, because they are too closely related and so genetically they might not be able to pollinate each other. However there are other fine crabapples that are not related to Honeycrisp that you might want to give a shot such as Dolgo. Dolgo is a good sized crabapple for eating (1.5 to 2 inch size) that should also be good for cooking and baking. This crab variety is available through Fedco Seeds & Trees, and they have many other crabapple varieties that might also be good in zone 4. I had thought Kerr might also work for you, but now I see that Kerr likewise is an offspring of Malinda so it might not be the greatest partner for Honeycrisp. But of course any other crab might also be fine -- it's just not easy to find a good crab that is also worthwhile to use for eating and cooking. That is why I would still personally pick a normal apple such as Cortland or the others that I mentioned previously so that you get nicer sized apples to use for everything that you might want to use them for in the future. Me? I'll be using my apples for eating, sauce, pies, and cider cider cider, so I have both Honeycrisp and Cortland, as well as others including Sweet 16, Foxwhelp, and Dolgo -- the last three of which will be primarily used in my family for making cider and not much of anything else, a few for eating maybe but mostly cider. So it all depends on what you really want to get out of all your apples.