This rough proof-of-concept seems to have the desired effect:

diff --git a/Python/marshal.c b/Python/marshal.c
index 1260704c74..70f9c4b109 100644
--- a/Python/marshal.c
+++ b/Python/marshal.c
@@ -503,9 +503,23 @@ w_complex_object(PyObject *v, char flag, WFILE *p)
             W_TYPE(TYPE_SET, p);
         n = PySet_GET_SIZE(v);
         W_SIZE(n, p);
-        while (_PySet_NextEntry(v, &pos, &value, &hash)) {
+        PyObject *pairs = PyList_New(0);
+        for (Py_ssize_t i = 0; _PySet_NextEntry(v, &pos, &value, &hash); i++) {
+            PyObject *pair = PyTuple_New(2);
+            PyObject *dump = PyMarshal_WriteObjectToString(value, p->version);
+            PyTuple_SET_ITEM(pair, 0, dump);
+            Py_INCREF(value);
+            PyTuple_SET_ITEM(pair, 1, value);
+            PyList_Append(pairs, pair);
+            Py_DECREF(pair);
+        }
+        PyList_Sort(pairs);
+        for (Py_ssize_t i = 0; i < n; i++) {
+            PyObject *pair = PyList_GET_ITEM(pairs, i);
+            PyObject *value = PyTuple_GET_ITEM(pair, 1);
             w_object(value, p);
         }
+        Py_DECREF(pairs);
     }
     else if (PyCode_Check(v)) {
         PyCodeObject *co = (PyCodeObject *)v;

I can clean it up and convert it to a PR if we decide we want to go this route.