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.

[1] http://blog.christianperone.com/2015/08/googles-s2-geometry-...