What is the most motivating way to introduce modular arithmetic?

What I find works with students is to hand them a problem they completely understand the meaning of and ask them to solve it. Before telling them anything about congruences, give them a couple of simple number theory problems to solve, which are hard to do without congruences. A brief excursion online produced these two -- there are thousands of others of course, you could pick anything that appeals to you.

Show that 3 divides $4^n -1$ for all integers n.

Show that $n^5 - n$ is divisible by 3 for all integers n.

Let them try to prove these things (or whatever you pick; these may be too easy). Then show them that there is an easier way. But first, of course, you have to introduce an idea. They may still squirm around while you are introducing congruences, but they'll come back to life when you start proving those problems.