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"][1], 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"][3] 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][4] (quadrilateralized spherical cube) -- an [equal-area projection of the sphere onto a cube][2] -- the 6 large squares divide easily into a nice square grid.
* [An icosahedron-based method for pixelizing the celestial sphere][5] -- 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?

  [1]: http://en.wikipedia.org/wiki/Natural_Area_Code
  [2]: http://www.progonos.com/furuti/MapProj/Normal/ProjPoly/projPoly2.html
  [3]: http://en.wikipedia.org/wiki/Thomson_problem
  [4]: http://en.wikipedia.org/wiki/Quadrilateralized_spherical_cube
  [5]: http://space.mit.edu/home/tegmark/icosahedron.html