How to sort objects from a collection using python?
Alright so what worked for me is this:

For every cubelet the cubelet.data.vertices are all in the same grid cell so to speak. That means it's not important which one of them I take to compare against other cubelets. If it was I could still iterate them and find a min/max/average to my desire.

So using cubelet.data.vertices[0].co works for selecting initial, unrotated cubelets, but it breaks once a cubelet is rotated. This makes sense as the rotation is part of the cubelet.matrix_world rather than the individual vertices being updated.

I've added an exampleVector function encapsulate finding an arbitrary example vector for a cubelet for comparison:

def exampleVector(cubelet):
    return cubelet.matrix_world @ cubelet.data.vertices[0].co


With this my cubeletsBySide function now looks like this:

def cubeletsBySide(cube, side):
    dimensionsBySide = {'U': 2, 'D': 2, 'F': 1, 'B': 1, 'R': 0, 'L': 0}
    revertBySide = {'U': True, 'D': False,
                    'F': True, 'B': False, 'R': False, 'L': True}
    dimension = dimensionsBySide[side]
    return sorted(
        list(cube.all_objects.values()),
        key=lambda c: exampleVector(c)[dimension],
        reverse=revertBySide[side])[:9]


Together with the rest of my code I can now perform the superflip again, which I use to verify that both side selection and rotations are working correctly:

superflip = ["R", "L", "U", "U", "F", "U'", "D", "F", "F", "R", "R", "B", "B", "L", "U", "U", "F'", "B'", "U", "R", "R", "D", "F", "F", "U", "R", "R", "U"]

currentCube = newCube('cube', (0, 0, 0))
shuffle(currentCube, superflip)