Induction is basically the first thing you learn in your freshman intro to proofs class. Probably US high school geometry classes teach it too, I don't remember, but it can be easily taught to sophomore high school students. So you saying it's not intuitive is a bias that came from your previous experience, not from reality.

Induction is literally the simplest type of proof you do in math, and of course there's a 1-1 relationship between induction and recursion. Induction is also the basic way that you discover/invent an algorithm in CS, which is usually taught in junior level CS algorithms classes in all the top colleges.

So I think it's just a problem with people just not learning a fairly simple concept or just skipping intro to algo classes altogether.

Induction should be intuitive. I think there are a few things that get lost. One is you need to show the steps are equivalent. You have to show going from n-1 to n is similar to going from n to n+1. My favorite analogy is coming stairs. You prove you can get from the floor to the first step (that is the base case) but you also have to show that all the stairs are identical. I think this is where a lot of people misunderstand induction.

It's a familiar concept to most people, though: most people understand that people have parents, grandparents, greatgrandparents, and so on.

(Maybe a bad example; I feel like it shows that people are familiar with coinduction.)