in principle it is always possible to improve over a randomized algorithm

in principle are the key words.

As the old saying goes, in theory there is no difference between theory and practice but in practice there is.

requires having some knowledge of the distribution over the environment, and that would break modularity.

You are using the word "modularity" in a sense weird to me. From my perspective, in the software context "modularity" refers to interactions of pieces of software, not inputs or distributions over the environment.