Ok so I spent a lot of time thinking and have come up with a solution.

I think the problem was that to make the tiles look 3D, I made them protrude outside the cell bounds, which messed up the ordering of the pixels, and the top of one tile would clash with the bottom of another. To fix this, I split the art up into the top and bottom of the tile, and made 2 separate tilemaps, one for the bottom and one for the top, and had the sorting layer higher on the top so that it always shows over the bottom.