Linking order will affect code and static data order and cache alignment in turn. Similarly, environment variables are pushed on the stack by the kernel. Their size will affect alignment of application data on the stack.

Maybe there are other causes as well.

Would it be possible to determine ahead of time what order would maximize performance, or would that require profiling?

I think at the very least, you'd need profiling to determine the hot code path, and that can change depending on input...