Q:

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

According to Wikipedia:

...proofs by mathematical induction
  have two parts: the "base case" that
  shows that the theorem is true for a
  particular initial value such as n = 0
  or n = 1 and then an inductive step
  that shows that if the theorem is true
  for a certain value of n, it is also
  true for the value n + 1.  The base
  case is often trivial and is
  identified as such, although there are
  cases where the base case is difficult
  but the inductive step is trivial. 

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

A:

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$.

A:

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...

A:

Caratheodory theorem about convex hull. 
The base case is to show that a point in the convex hull of $n+2$ points of a $n$ dimentional affine space, is in fact in the convex hull of $n+1$ points.