Here is one I've thought of a while ago for my combinatorics classes, but never ended up using.
Let $C_{0},C_{1},C_{2},\ldots$ be the Catalan numbers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$.
Theorem 1. For each $n\in\mathbb{N}$, we have \begin{align*} C_{n+1}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }2^{n-2k}\dbinom{n}{2k} C_{k}. \end{align*}
This is Theorem 6.1 in Elena Barcucci and M. Cecilia Verri, Some more properties of Catalan numbers, Discrete Mathematics 102, Issue 3, 22 May 1992, pp. 229--237. They ascribe the theorem to Touchard and give a combinatorial proof. Here is a simple bijective proof that is nowadays folklore:
Proof of Theorem 1 (sketched). Consider the set $\mathbb{Z}\times\mathbb{N}$ of all pairs $\left( i,j\right) $ of integers with $j\geq0$. View this set as a subset of the Cartesian plane $\mathbb{R}^{2}$. Consider paths on the set $\mathbb{Z}\times\mathbb{N}$ that consist of the following four kinds of steps:
A U-step (short for up-step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j+1\right) $.
A D-step (short for down-step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j-1\right) $.
A G-step (short for green horizontal step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j\right) $.
An R-step (short for red horizontal step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j\right) $.
Thus, G-steps and R-steps connect the same points, but we distinguish between them nevertheless. Paths using these steps (and starting and ending on the x-axis) are called bicolored Motzkin paths. Paths using only D-steps and U-steps (and starting and ending on the x-axis) are called Dyck paths. The number of Dyck paths from $\left( 0,0\right) $ to $\left( 2k,0\right) $ is known to be $C_{k}$.
Now, how many bicolored Motzkin paths are there from $\left( 0,0\right) $ to $\left( n,0\right) $ ? On the one hand, this number is $\sum\limits_{k=0} ^{\left\lfloor n/2\right\rfloor }\dbinom{n}{2k}2^{n-2k}C_{k}$, because we first choose how many U-steps our path will have (let's say this number will be $k$), then choose the positions of the $k$ U-steps and the $k$ D-steps (we need the same amount because the path has to start and end at the same height), then choose the "colors" of the remaining steps (i.e., which of them will be G-steps and which will be R-steps), and finally choose the U-steps and the D-steps (this is tantamount to choosing a Dyck path from $\left( 0,0\right) $ to $\left( 2k,0\right) $, because removing all the G-steps and R-steps will result in such a Dyck path). Thus, we get $\sum\limits_{k=0} ^{\left\lfloor n/2\right\rfloor }\dbinom{n}{2k}2^{n-2k}C_{k}$.
On the other hand, there is a bijection from the set $\left\{ \text{bicolored Motzkin paths from }\left( 0,0\right) \text{ to }\left( n,0\right) \right\} $ to the set $\left\{ \text{Dyck paths from }\left( 0,0\right) \text{ to }\left( 2n+2,0\right) \right\} $. Indeed, this bijection sends a bicolored Motzkin path $\mathbf{m}$ to a Dyck path $\mathbf{d}$ that is constructed as follows:
Start with an U-step.
Look at each step of $\mathbb{m}$ in order (from left to right). For each step of $\mathbf{m}$, make the following two steps: If the step of $\mathbf{m}$ is an U-step, then make two U-steps. If the step of $\mathbf{m}$ is a D-step, then make two D-steps. If the step of $\mathbf{m}$ is a G-step, then make a U-step followed by a D-step. If the step of $\mathbf{m}$ is an R-step, then make a D-step followed by a U-step.
Finish with a D-step.
It is easy to see that the resulting path $\mathbf{d}$ will really be a Dyck path from $\left( 0,0\right) $ to $\left( 2n+2,0\right) $. (Note that each pair of steps of $\mathbf{d}$ coming from a step of $\mathbf{m}$ starts at odd height, so the initial D-step cannot lead you below the x-axis.) It is furthermore not hard to see that this assignment of $\mathbf{d}$ to $\mathbf{m}$ is a bijection. (Indeed, any pair of two consecutive steps of a Dyck path is either UU or DD or UD or DU; moreover, if we focus on the pairs consisting of a $2i$-th step and the $\left( 2i+1\right) $-st step for all $i\in\left\{ 1,2,\ldots,k\right\} $, then the number of DD pairs cannot exceed the number of UU pairs.) Thus, we have found a bijection from $\left\{ \text{bicolored Motzkin paths from }\left( 0,0\right) \text{ to }\left( n,0\right) \right\} $ to $\left\{ \text{Dyck paths from }\left( 0,0\right) \text{ to }\left( 2n+2,0\right) \right\} $. Hence, the number of bicolored Motzkin paths from $\left( 0,0\right) $ to $\left( n,0\right) $ is the number of Dyck paths from $\left( 0,0\right) $ to $\left( 2n+2,0\right) $; but the latter number is $C_{n+1}$.
Thus, we have counted the former number in two ways. Comparing the results, we find \begin{align*} C_{n+1}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }\dbinom{n}{2k}2^{n-2k} C_{k}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }2^{n-2k}\dbinom{n}{2k}C_{k}. \end{align*} This proves Theorem 1. $\blacksquare$
Now, let us fix an $n\in\mathbb{N}$, and ask ourselves when $C_{n+1}$ is odd. Theorem 1 yields \begin{align*} C_{n+1}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }2^{n-2k}\dbinom{n}{2k} C_{k}. \end{align*} The $2^{n-2k}$ factors ensure that all addends on the right hand side of this equality are even, except possibly the addend for $k=n/2$ (because here the $2^{n-2k}$ factor becomes $1$). This latter addend only exists when $n$ is even, and in that case equals $\underbrace{2^{n-2\left( n/2\right) }} _{=1}\underbrace{\dbinom{n}{2\left( n/2\right) }}_{=1}C_{n/2}=C_{n/2}$. Thus, we conclude that
the number $C_{n+1}$ is even when $n$ is odd;
we have $C_{n+1}\equiv C_{n/2} \mod 2$ when $n$ is even.
Using these two facts, we can now easily prove (by induction on $r$ and strong induction on $m$) that
the number $C_{2^{r}-1}$ is odd for each nonnegative integer $r$;
the number $C_{m}$ is even whenever $m\in\mathbb{N}\setminus\left\{ 2^{r}-1\ \mid\ r\in\mathbb{N}\right\} $.
(Indeed, if $m\in\mathbb{N}\setminus\left\{ 2^{r}-1\ \mid\ r\in \mathbb{N}\right\} $, then either $m-1$ is even, or else $\left( m-1\right) /2\in\mathbb{N}\setminus\left\{ 2^{r}-1\ \mid\ r\in\mathbb{N}\right\} $, in which case we can apply the congruence $C_{n+1}\equiv C_{n/2} \mod 2$ for $n=m-1$ and then conclude using the induction hypothesis.)
I suspect that higher congruences for Catalan numbers (modulo $2^k$) can also be established using Theorem 1.