However, using a Hilbert Curve for sharding doesn't seem like the best approach.
Yes, that's also what I thought. Searching for "same size k-means" yields a simple postprocessing step to even out the clusters produced by the usual k-means algorithm.
EDIT: k-means is adapted directly here: https://elki-project.github.io/tutorial/same-size_k_means