Take AC0. What is a natural thought process that leads to the definition of AC0? Does this class arise intrinsically anywhere?
The logarithmic time hierarchy (LH) is equal to uniform $\mathbf{AC}^0$. A natural thought process that leads to LH is to look for an analogy of the polynomial time hierarchy (PH) for logarithmic time. You can prove that LH does not collapse1, and that its level structure carries over to $\mathbf{AC}^0$. Some problems like addition are in $\mathbf{AC}^0$, but provably not in $\mathbf{NC}^0$. Neither addition nor any other single problem is complete for uniform $\mathbf{AC}^0$, since otherwise LH would collapse. Barrington et al. showed that Searching constant width mazes captures the $\mathbf{AC}^0$ hierarchy, so this class arises intrinsically at least sometimes. But that is not the normal case, where $\mathbf{AC}^0$ is used out of convention (instead of a specific depth $k$-subclass). I guess the reason for that convention is that $\mathbf{AC}^0$ is provably a proper subset of $\mathbf{ACC}^0$, so it is weak enough to convey the important point. And $\mathbf{AC}^0$ is closed under composition, which is nice for $\mathbf{AC}^0$ reductions between problems.
My problem is that in the case of unbounded fan-in, AND and OR gates behave very differently. Why do we take these gates along with NOT to define a circuit class?
You probably mean that they behave very different from bounded fan-in gates. I guess $\mathbf{NC}^0$ is too weak and $\mathbf{NC}^1$ is too strong for describing real hardware (circuits). Real hardware needs at least addition and storage-access (multiplexer), which are both in $\mathbf{AC}^0$. Other nice to have functionality like multiplication and division is in $\mathbf{TC}^0$. It would be interesting whether current hardware contains any functionality (i.e. "fast" processor instruction) not in $\mathbf{TC}^0$. At least I am not aware of any.
It should be clear that $\mathbf{AC}^0$, $\mathbf{TC}^0$, and $\mathbf{NC}^1$ are models of parallel computation, especially in their non-uniform version as implemented in actual hardware. I wrote about dreams of fast solutions in the sense of allowing software the same parallel capabilities like hardware already has today. I am still working through all the material referenced there, but at least I have worked through Algebra, Logic and Complexity in Celebration of Eric Allender and Mike Saks by Neil Immerman. The last slides describe a typical place where $\mathbf{AC}^0$ occurs, namely all "natural" NP complete problem stay complete under $\mathbf{AC}^0$ reductions, and all such problems are actually $\mathbf{AC}^0$ isomorphic. Also true for $\mathbf{NC}^1$, $\mathbf{sAC}^1$, L, NL, P, PSPACE, etc (complete problems). Edit (in response to Kaveh): The original statement of that theorem can be found in Reducing the Complexity of Reductions by M. Agrawala, E. Allender, R. Impagliazzo, T. Pitassi, S. Rudich from 2001:
More precisely, we show that for any class $\mathcal{C}$ closed under uniform $\mathbf{TC}^0$-computable many-one reductions, the following three theorems hold:
- ...
- The sets complete for $\mathcal{C}$ under P-uniform $\mathbf{AC}^0$ reductions are all isomorphic under isomorphisms computable and invertible by P-uniform $\mathbf{AC}^0$ circuits of depth-three.
- There are sets complete for $\mathcal{C}$ under Dlogtime-uniform $\mathbf{AC}^0$ reductions that are not isomorphic under any isomorphism computed by (even non-uniform) $\mathbf{AC}^0$ circuits of depth two.
The fact that P-uniform $\mathbf{AC}^0$ circuits are needed is slightly unexpected, since uniform $\mathbf{AC}^0$ normally means Dlogtime-uniform $\mathbf{AC}^0$ (i.e. FOL and LH are only known to be equal to Dlogtime-uniform $\mathbf{AC}^0$, not to P-uniform $\mathbf{AC}^0$). Manindra Agrawal, The First-Order Isomorphism Theorem. FSTTCS 2001, LNCS 2245: 70-82, is mentioned last in Immerman's survey, since it seems to prove that P-uniform can be replaced by Dlogtime-uniform. But it doesn't preserve the depth-three part of the theorem. There are surveys by Manindra Agrawal (2009) and Eric Allender (2014), but I only found them after writing this answer (while trying to understand whether Kaveh's point about the supreme importance of FOL is correct), and I have not read them yet.
1M. Sipser. Borel sets and circuit complexity. In Proceedings, 15th ACM Symposium on the Theory of Computing, 1983