This is my first visit to MO, so I have to apologize for making this an "answer": it is just a comment on Nik Weaver's suggestion.
I don't think that NW's conjecture is much different from the original question. Indeed, you comment that it is different because f should work against all permutations g. But in fact you restrict to those g that have C_g bounded by a universal constant (say, 2). This is a very small set, it is even compact in the natural topology relevant to the action on Z^d (which is the action underlying the whole question). Therefore, it is not so different from considering finitely many g's and thus from the original question.
Anyway, this is my intuition, it is not a mathematical statement. Nicolas Monod
[Edit after reading NW's argument]: at first sight, it seems that your reduction to your conjecture is indeed just exploiting that the set C_g less than a constant is compact (approximation argument).