How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?
There's an enormous amount of work on data structures and algorithms for this sort of problem.  I suggest you start by reading the general literature on this problem.

Start by reading about algorithms for nearest neighbor search, including all nearest neighbors and the fixed-radius nearest neighbors problem.  Those techniques are applicable to your problem.

Then, read about quadtrees, octrees, k-d trees, VP trees, and the general category of BSP trees.