Is there a high-concept explanation for why characteristic 2 is special?

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 ${\bf 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 ${\bf 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.

Maybe this isn't very high concept, but I've always thought the "original sin" of $2$ was that there's a integer which is a second root of unity, which doesn't happen for any other prime.

Why is this deep? Well, one way to think of it as this: in fields of characteristic $p$, $p^\text{th}$ roots of unity must all be trivial (and in general, taking $p^\text{th}$ roots is a bad idea), so fields of characteristic $2$ are particularly incompatible with the integers, since they have to destroy $-1$.

I think $2$ is not special, we just see the weirdness at $2$ earlier than the weirdness at odd primes.

For example, consider $\operatorname{Ext}_{E(x)}(\mathbb{F}_p , \mathbb{F}_p)$ where $E(x)$ denotes an exterior algebra over $\mathbb{F}_p.$ If $p=2$ this is a polynomial algebra on a class $x_1$ in degree $1$ and if $p$ is odd this is an exterior algebra on a class $x_1$ tensor a polynomial algebra on $x_2$. I say these are the same, generated by $x_1$ and $x_2$ in both cases and with a $p$-fold Massey product $\langle x_1,\dotsc,x_1 \rangle = x_2.$ The only difference is that a $2$-fold Massey product is simply a product.

In what sense are the $p$-adic integers $\mathbb{Z}_p$ the same? One way to say it is that if you study the algebraic $K$-theory of $\mathbb{Z}_p$ you find that the first torsion is in degree $2p-3$. If $p=2$ this is degree $1$, and $K_1(A)$ measures the units of $A$ (for a reasonable ring $A$). If $p$ is odd it measures something something more complicated. Another way to say it is that $\mathbb{Z}_p$ is the first Morava stabilizer algebra and there is something special about the $n^\text{th}$ Morava stabilizer algebra at $p$ if $p-1$ divides $n$. If you study something like topological modular forms, this means the primes $2$ and $3$ are special.

The dual Steenrod algebra is generated by $\xi_i$ at $p=2$ and by $\xi_i$ and $\tau_i$ at odd primes. But really it is generated by $\tau_i$ with a $p$-fold Massey product $\langle\tau_i,\dotsc,\tau_i\rangle = \xi_{i+1}$ at all primes, after renaming the generators at $p=2$. (Again a $2$-fold Massey product is just a product.)

I could go on, but maybe this is enough for now.