wOk, I now understand what's happening. The defaults produce only 2 bins which turns 

 - cat1 and cat2 into 1 2 2 1 2 2 1 2 2 
 - cat3 into 2 2 1 2 2 1 2 2 1 

which explains the lower mutual information value (it is indeed not related to sort order!).
Allowing 3 bins by modifying one line of code like so

    cor.matrix.nats <- (mutinformation(discretize(df, disc="equalwidth", nbins=NROW(df)^(1/2))))

bins

 - cat1 and cat2 into 1 2 3 1 2 3 1 2 3 
 - cat3 into 3 2 1 3 2 1 3 2 1 

and now mutual information cat1 vs. cat2 = cat1 vs. cat3 = 1.0986123.

Guess I need to think about how to get a robust value for  `nbins` in  `discretize` not knowing in advance how many real bins across how many samples are coming in...