What are some examples of induction where the base case is difficult but the inductive step is trivial?

Bolzano-Weierstrass theorem: every bounded sequence in $\mathbb{R}^n$ has a convergent subsequence.

The inductive step is very easy and most of the work is in showing that this is true for $n=1$.

The proof that all horses are the same color. The base case is $n=2$; prove that every set of $2$ horses is a set of horses all of the same color. If you can prove that, the induction step is a breeze; in any set of $n+1$ horses, remove one horse, the rest are all of the same color, then put that horse back in and remove a different one, again getting a set of horses all of the same color, and note that since $n+1\ge3$ there's at least one horse in both of the size $n$ sets, so all $n+1$ horses are of the same color.

But that base case is really, really difficult!

In fact, you might say it's a horse of a different color...

The Product Rule, $$(f_1f_2\cdots f_n)'=f_1'f_2\cdots f_n+\cdots+f_1f_2\cdots f_n'$$ To prove the base case, $n=2$, $(fg)'=f'g+fg'$, you need to apply the definition of the derivative, and properties of limits. But then you can deduce the $n+1$ case very simply from the base case and the induction hypothesis: $$(f_1f_2\cdots f_{n+1})'=\bigl((f_1f_2\cdots f_n)(f_{n+1})\bigr)'=(f_1f_2\cdots f_n)'f_{n+1}+(f_1f_2\cdots f_n)f'_{n+1}, {\rm\ etc.}$$