I think there are two phenomena at work, and often one can separate behaviors based on whether they are "caused by" one or the other (or both). One phenomenon is the smallness of $2$, i.e., the expression $p-1$ shows up when describing many characteristic $p$ and $p$-adic structures, and the qualitative properties of these structures will change a lot depending on whether $p-1$ is one or greater than one. For example:

 - Adding a primitive $p^\text{th}$ root of unity $z$ to $\mathbb{Q}_p$ yields a totally ramified field extension of degree $p-1$. The valuation of $1-z$ is $1/(p-1)$ times the valuation of $p$. This is a long way of saying that $-1$ lies in $\mathbb{Q}_2$.
 - The group of units in the prime field of a characteristic $p$ field has order $p-1$.  This is the difference between triviality and nontriviality.
 - As you mentioned, some combinatorial questions can be phrased in Boolean language and attacked with linear algebra.

The other phenomenon is the evenness of $2$. Standard examples:

 - Negation has a nontrivial fixed point.  This gives one way to explain why there are $4$ square roots of $1 \pmod 2^n$ (for $n$ large), but only $2$ in the $2$-adic limit.  If you combine this with smallness, you find that negation does nothing, and this adds a lot of subtlety to the study of algebraic groups (or generally, vector spaces with forms).
 - The Hasse invariant is a weight $p-1$ modular form, and odd weight forms behave differently from even weight forms, especially in terms of lifting to characteristic zero, level 1. This is a bit related to David's mention of abelian varieties - I've heard that some Albanese "varieties" in characteristic $2$ are non-reduced.