We dealt with the probabilistic method in our undergrad randomized algorithms class at Berkeley, and used Mitzenmacher's book. Chapter 6 is about the probabilistic method and has a bunch of exercises that don't require as much computational yoga as Olympiad problems or Alon and Spencer.
The chapter is mostly about combinatorics, and not about algorithms. For instance, one of the questions in Chapter 6 is to show if $4 \binom{k}{2} \binom{n}{k-2} 2^{1-\binom{k}{2}} \leq 1$, then it's possible to two-color the edges of $K_n$ so there's no monochromatic $K_k$ subgraph, which is a direct application of Lovasz.
