Can changing the order of adjectives alter the literal meaning of a phrase?

In describing books,

my collectible first editions

would mean the earliest printing of the books, whereas

my first collectible editions

would mean the books that the speaker collected the earliest.

And it's not just because "first edition" is a technical term. "My horrible first year at college" is different from "My first horrible year at college" for the same reason.

EDIT: I've found another, quite different, and possibly better, example. Consider

poor unfortunate men

and

unfortunate poor men

(And if anybody thinks I cribbed this example from Disney's The Little Mermaid, they're completely correct.)

In the first, poor means pitiful and in the second, it means impoverished.

Why? I think it has to do with natural adjective order—in poor unfortunate men, the adjective poor is an opinion, which comes first in the order; while in unfortunate poor men, the adjective poor comes after unfortunate, so it has to be a quality (like unfortunate) and not an opinion.

The same thing happens, even less ambiguously, if you use tiny rather than unfortunate, because in the adjective order, size comes between opinion and quality. So in

poor tiny men

poor means pitiful, while in

tiny poor men

it means impoverished.

As pointed out elsewhere, “'local crumbed scallops' would be already-crumbed scallops obtained locally; 'crumbed local scallops' would be scallops obtained locally and then crumbed after being obtained”.

Generally speaking, there is a natural adjective order in English, which is everything but commutative. And “I saw a brown big spider” strikes me as ungrammatical.

Sure, as others have pointed out already, you can make it grammatical by putting the stress on brown, and regarding big spider as a single fixed unit. But that's precisely the thing: you have to jump through hoops, and even then it means something slightly different. (Yes, as you have pointed out in a comment, in a row of spiders it might still point out the exact same spider; but it is not saying the exact same thing about that spider.)

First off, an interesting aside. Someone else pondering your question led indirectly to the creation of the entire fantasy genre:

"I first tried to write a story when I was about seven. It was about a dragon. I remember nothing about it except a philological fact. My mother said nothing about the dragon, but pointed out that one could not say 'a green great dragon', but had to say 'a great green dragon'. I wondered why, and still do. The fact that I remember this is possibly significant, as I do not think I ever tried to write a story again for many years, and was taken up with language."

From "Letters of J.R.R. Tolkien".

To answer your question:

Are there instances in which adjectives are non-commutative, so that permuting the order of the adjectives changes the literal meaning of what's being said?

Yes, lots. For example, consider the mathematician's definition of "diameter". Suppose you have a shape -- any shape, in any number of dimensions -- and you want to find its diameter. How can we define diameter on an arbitrary shape?

It's actually straightforward. Consider every possible pair of points on the object, and consider every possible "path" between those two points. For each pair of points, find the shortest of those paths. The length of that path is the shortest distance between those two points. Now find the pair of points that has the longest shortest path between them. The length of that path is the diameter.

Clearly the "longest shortest path" is very different than the "shortest longest path".

See also my article about finding the longest shortest shortest path between poppyseeds on a bagel, if this subject interests you.