I think Godel's completeness theorem is very intuitive. For example, can you imagine a first order theorem that would be true for all groups, that you wouldn't be able to prove (by Godel's definition of `prove'). Of course not! But the proof of the completeness theorem is hard.