Why must the field equations be differential? In Landau–Lifshitz's Course of Theoretical Physics, Vol. 2 (‘Classical Fields Theory’), Ch. IV, § 27, there is an explanation why the field equations should be linear differential equations. It goes like this:

Every solution of the field equations gives a field that can exist in nature. According to the principle of superposition, the sum of any such fields must be a field that can exist in nature, that is, must satisfy the field equations.
As is well known, linear differential equations have just this property, that the sum of any solutions is also a solution. Consequently, the field equations must be linear differential equation.

Actually, this reasoning is not logically valid. Not only the authors forget to explain the word ‘differential’, but they also do not actually prove that the field equations must be linear. (Just in case: this observation is not due to me.) But it seems that the last issue can be easily overcome. However, it is exactly the word ‘differential’, not ‘linear’, that is bothering me.
There is a nice theorem of Peetre stating that the linear operator $D$ that acts on (the ring of) functions and does not increase supports, that is, $\mathop{\mathrm{supp}} f \supset \mathop{\mathrm{supp}} Df$, must be a differential operator. The property of preserving supports can be considered as a certain locality property. Hence, the field equations must be differential because all interactions must propagate with a finite velocity.
But there is another notion of ‘locality’ of an operator: the operator $D$ is called local if the function $Df$ in the neighbourhood $V$ can be computed with $f$ determined only on $V$ as well, i.e., $(Df)|_V$ is completely defined by $f|_V$. The locality in this sense is not equivalent to the locality in the sense of supports' preserving. (Unfortunately, I do not have an illustrative example at hand right now, so there is a possibility of mistake $M$ hiding here.)
The question is: what physical circumstances determine the (correct one) notion of locality for a given physical problem? (Assuming there is no mistake $M$.) And does my reasoning really justifies the word ‘differential’ in the context of field equations? If so, are there any references containing more accurate argument than the one presented in Landau–Lifshitz's Course?
 A: This does not really answer your question why the equation should be differential. But
I think that the two notions of locality you mentioned are just equivalent, if I am not mistaken.
Let us prove that the second definition impies the first one. One has to show that if a point $x$ does not belong to $supp(f)$ then $x$ does not belong to $supp(Df)$. Indeed, then there exists an open neighborhood $V$ of $x$ such that $f|_V=0$. Hence by the assumption $Df|_V=0$. Hence $x\not\in supp(Df)$ as requested.
Let us prove now the converse statement that the first definition implies the second one. Assume that $f|_V=g|_V$. Then $(f-g)|_V=0$. Hence $supp(f-g)\cap V=\emptyset$. Consequently $supp(D(f-g))\cap V=\emptyset$, i.e. $D(f-g)|_V=0$. That means that $Df|_V=Dg|_V$.
A: All physical phenomena occur on a substrate, medium or 'space'. This space has properties which guarantee the stability of the system, such as the existence of a characteristic
 propagation speed of 'c'. The reaction allowed at each point in space, and at every moment, is strictly due to the local environment, its immediate neighborhood and so 'action at a distance' is not permitted, nor infinities.
This physical environment (1D) is illustrated in this image (by Hans de Vries) and found in his online book "Understanding Relativistic Quantum Field Theory". This medium allows the propagation of the classical wave equation 
$$\frac{\partial^{2}\psi}{\partial t^{2}}=c^{2}\frac{\partial^{2}\psi}{\partial\mathit{x}^{2}}$$

ψ is the vertical displacement in the mechanical model. ...the
  equation is satisfied by any arbitrary function which shifts along
  with a speed v (or −v). A function ”stretched” by a factor v has it’s
  slopes decreased by a factor v, while it’s second order derivatives
  are lower by a factor $v^2$ .

A: Not all fields follow the superposition principle. A temperature field does not. A pressure field does, etc.
Those words in Landau–Lifshitz's book are an attempt to "substantiate" equations obtained mostly empirically in the frame of a differential approach.
A: It is not clear what the physical meaning of local should be.  There is a large literature on this, and not any overwhelming consensus.  See my own question, where I accepted what seemed like the best answer although nothing really got completely settled.
Locality in Quantum Mechanics
The reference provided me was extremely interesting, see arXiv:quant-ph/9809030
Furthermore, the position operators that have been proposed for Relativistic Particle Mechanics have very inconvenient non-locality properties.  Furthermore furthermore, it is a myth that special relativity forbids propagation of information faster than the speed of light, as has been shown by Prof. Geroch of Chicago in «¿Faster than Light?» http://arxiv.org/abs/1005.1614
so the physical basis of what locality should be is rather complicated...and not yet clear to me.
A: Note the answer by @MKO proving that the definitions of locality are equivalent. That said, not all field theories bring to linear operators (e.g. General Relativity), so you cannot use the argument of linearity in general.
Indeed one sometimes has algebraic equations for some fields; in all the examples I can name these fields are redundant though, meaning they do not convey any information about the dynamics of the system.
If you think about it differential operators are the most general local operators that you can build with a given set of functions on a "nice enough" space (connected and maybe even smooth?). Of course I am including algebraic (order zero) operators.
So when describing local dynamics you can either have a (really) differential operator (order $\geq 1$) or a simply algebraic operator. But algebraic equations fix the system without giving you possibility to determine the initial data, so they are constraints.
This reasoning seems to leave only differential operators.
Truth is, you could still write algebraic equations bringing to the solution for the dynamics of the system by including the arbitrary constants that will serve as initial data. But being able to write such a system of equations means that one already knows the form of the solution: the operators you are using will need to contain the explicit form of the solution in some way.
Therefore, using algebraic equation is not much different from having the final solutions already written down (maybe rearranged in a messy way).
A theory that predicts something will need to be different. Ergo, if the space and the fields are "nice enough" (the usual case of field theory, no lattice or anything weird), you are left with differential operators. They are just the most generic operators using the information contained in the fields locally (i.e. neighborhood by neighborhood).
