I think induction should be taught first, and then loop invariants, since you usually need induction to prove that the loop invariant is really an invariant, and also because you need induction for other purposes than just proving that a loop invariant is really an invariant. In fact, in most curricula for Computer Science at university will have some math class that covers induction before a Algorithm Correctness course.
If this isn't the case, you might want to teach induction with some other examples first.
For example, proving that $1+2+\cdots+n = \frac{n(n+1)}{2}$ and a few other, relatively simple induction statements (e.g. sums, divisions, inequalities). If you need to teach recurrence relations as well, then you might introduce them now as well since you sometimes need induction to solve them. I think it is also helpful for the intuition to explain the domino-effect: $P(1)$ implies $P(2)$, $P(2)$ implies $P(3)$, $P(3)$ implies $P(4)$, etc. (also with a concrete example). This also shows the importance of the base case in the induction.
Then, loop invariants.
I would again (as always, actually) start with some easy examples, for example:
x=0
while (x < 2)
x = x+1
with the invariant being $x \leq 2$. How to find this? Well, just go through the loop. In this case this is doable: $x=0$ becomes $x=1$ becomes $x=2$. Now show them you don't really need to do the whole loop if you have while (x<100), for example. Now it is time to mention induction again: Since you don't want to write all hundred steps, you can use induction to prove this loop invariant.
Students now might think they just need to replace the lesser than with lesser than or equals. Show them this isn't true with an example like this (or use lesser than or equals in the statement):
x=0
while (x < 9)
x = x+2
Now, it is probably time for some complexer examples.
