How can I stop these weird gaps between equally-spaced sprites?

I have a grid of sprites, they are all the same size and spaced equally apart. But at most orthographic sizes, larger gaps appear between the sprites.

I've noticed turning anti aliasing property in the quality settings to 8x multi sampling does fix the issue, but I'm worried about performance and compatibility with Android devices.

Thank you very much.

Here is a .gif showing how it looks when I change the orthgraphic size: http://i.imgur.com/Dpycu3r.gif