There is a perfect command for that hidden in the Cartographic Toolbox.
Cartography Tools>Generalization>Create Cartographic Partitions
The only catch is that it requires at least 50,000 points to run. But you could write a similar script yourself.
It works by creating a bounding box and then quartering it and counting the number in each quarter.
Then cycle through each new quadrant and quarter it again until it meets the maximum count.
the main tool does not dissolve out squares with too few, but you could do that.