S2 wouldn't be a bad choice, it lets you compute "coverings" of arbitrary regions as S2 cells, with variable resolution. Fixed size is trickier but is probably doable, especially if you're allowed to null out unused cells. Check out https://s2.sidewalklabs.com/regioncoverer/

Depends on where the land is and size and shape of the polygons are

Let's say the land is confined to north America, the size can vary from an entire state to a single zip code (I know zips are logical addressing, not geological, but I have what I have), and the shape is unrestricted so it could be non-convex. I suppose one could convert various kinds of areas (states, cities, boroughs, ...) to lists of zipcodes contained within and OHE them but I feel like that would be the _worst_ solution.

I would probably use h3 for this which each polygon being reduced to a list of hex ids.