I am looking for examples of conjectures and famously hard-to-prove theorems which can be stated in the form:
For each natural number $n$, $P(n)$.
where $P$ is a predicate of natural numbers that is either (1) known to be decidable, or at least (2) known to be semi-decidable, and can be more or less easily shown to be true for many small natural numbers (and can be shown to be true for all numbers for which it is true).
Conjectures and theorems of the form
There are infinitely many natural numbers $n$ such that $P(n)$.
also fit the case (2) if the property $P$ is decidable or semi-decidable.
Examples for the case (1) with decidable $P$ are preferable, because in such case the conjecture can be easily disproved by a counterexample. It is also preferable that the conjecture could be easily explained to non-specialists.
So, Fermat's conjecture does not fit, but Goldbach's conjecture and Collatz conjecture do.
Goldbach's conjecture. Every even integer greater than 2 can be written as the sum of two primes.
Collatz conjecture. Start from any natural number. If the number is even, divide it by $2$. If it is odd, multiply it by $3$ and add $1$. Repeat. After repeating enough times, the number $1$ will appear in the sequence.
I think that examples of that kind can be useful when discussing mathematics with people who believe that to prove something it is enough to test sufficiently many times.