Unfortunately, the sphere is not a "developable surface". This fact has annoyed map-makers for more than a millennium.
I find your focus on "cells" fascinating. Most people seem fixated on trying to get points on the globe to correspond with points on a flat image, and don't seem concerned about dividing it up into areas. The simplest way to convert (lat,long) coordinates to standardized areas is the "Natural Area Code", but it has the same problems near the poles as latitude and longitude.
Your "too many close grid cells" and "Distance between a cell and a point" criteria reminds me of the "Thomson problem". I suspect you're trying to rule-out map projections like the Gall–Peters projection that, while they do have nice "equal area" properties, end up having a hundred little squares at the top and bottom of the on the map projected to a hundred long, narrow pie-slices that all touch a pole of the globe.
Perhaps you could pick one of the known solutions to the "Thomson problem" to build a nice grid. Most of those solutions look similar to a geodesic sphere -- but there are a few exceptions.
Perhaps the most famous application for "almost equal" patches is the Cosmic Background Explorer (COBE), which has inspired several mappings:
- the COBE sky cube (quadrilateralized spherical cube) -- an equal-area projection of the sphere onto a cube -- the 6 large squares divide easily into a nice square grid.
- An icosahedron-based method for pixelizing the celestial sphere -- an equal-area projection of the sphere onto an icosahedron -- the 20 large equilateral triangles divide easily into a nice equilateral triangle grid; or into a nice regular hexagonal grid.
- the HEALPix projection
The COBE "bins" are, as far as I can tell, a synonym for your "cells".
Are those COBE-inspired mappings adequate for you?