Treating texture units as levels in a tree and do a sorted depth-first traversal is a good starting point.
Ideally what you want to do is minimize the number of texture unit state changes which may mean that the same texture gets selected and deselected multiple times in the optimal case. You suggestion of sorting the tuples of texture IDs is a good idea as well.