The smallest is:

(M,N) = (101, 110)

(M^3,N^3) = (1030301, 1331000)

And the next is:

(M,N) = (102, 201)

(M^3,N^3) = (1061208, 8120601)

Algorithm notes:

To determine if the digits are a rearrangement, encode each integer or cube to a string of its alphabetically sorted digits - after sorting, there may be a leading zero, so this 'key' needs to be a string rather than an integer.

For integers up to 1000, 84% have a "buddy", or can be converted to another integer by rearranging the digits.

But this is only true for 4% of cubes of integers up to 1000.

Make the first filter: eliminating cube "keys" which only have a single cube associated with them.

-------------------

big = 1000

numbDict = {}

cubeDict = {}

for k in range(1,big):

    kCubed = k**3

    numbKey = ''.join(sorted(str(k)))

    cubeKey = ''.join(sorted(str(kCubed)))

    if numbKey not in numbDict:

        numbDict[numbKey] = [k]

    else:

        numbDict[numbKey].append(k)

    if cubeKey not in cubeDict:

        cubeDict[cubeKey] = [kCubed]

    else:

        cubeDict[cubeKey].append(kCubed)

for k,v in cubeDict.items():

    if len(v) == 1:

        continue

    these_N_keys = []

    thesenumbs = []

    for cub in v:

        n = round(cub**(1/3))

        keyOfN =  ''.join(sorted(str(n)))

        these_N_keys.append(keyOfN)

        thesenumbs.append(n)

    if len(these_N_keys) == len(set(these_N_keys)):

        continue

        

    print('M and N are among:', thesenumbs )

    print('The cubes are among:', v)

    print()