I'm surprised there's no mention of a rather successful and efficient way of doing this in the real world: Google's S2 geometry library [1]. Basically the earth can be covered in almost aquare tiles down to about 1cm^2 with 64 bit integers.
(Author here) S2 is great (and Eric is brilliant). It uses a cube projection underneath. S2 solves some problems I didn't have (equal area, curve filling) but the main problem I was looking at was the nonuniform connectivity, and as far as I can tell, it's the same with S2 as if you use a cube directly.
The special sauce in S2 is the space filling curve aspect of it which is totally not what you want here, the concept behind it is I want to say called a 'geo grid' which off the top of my head a guy I know made a library for [1].
[1] http://blog.christianperone.com/2015/08/googles-s2-geometry-...