How about using slices.Sort?

func (m Map) String() string {
    vs := []string{}
    for k, v := range m {
        vs = append(vs, fmt.Sprintf("%s:%s", k.String(), v.String()))
    }
    slices.Sort(vs)
    return fmt.Sprintf("{%s}", strings.Join(vs, ","))
}

Note for your Map that “If the key type is an interface type, [the comparison operators == and !=] must be defined for the dynamic key values; failure will cause a run-time panic.”