Your baby's behavior is not unusual, although different kids have very different tolerances. Our eldest daughter spent the first 3 months of her life in the hospital, and as a result is actually more comfortable with strangers than we are. Our youngest is the exact opposite. However, that doesn't mean you can't gradually teach them to overcome their fears.
You didn't describe your own reaction, which is important because infants learn by example. One common mistake parents, especially new parents, often make when their child has issues like this is trying to sneak out to avoid a scene, then the instant the baby cries they rush back and snatch him out of the arms of whoever is holding him. I don't know if that's what you do, but that's usually what people mean by "over-cuddling." It teaches your baby that you are also uncomfortable with the situation. It's also scary to look around and suddenly your parents are gone.
It's better to let him see you leave, and that you are happy and comfortable with leaving him in someone else's care. Yes, he will still cry, but don't come to his rescue immediately. Give him around 30 seconds, then come back in and don't snatch him away, but sit where he can see you and show you are comfortable with him being held by someone else.
It also helps to teach people the best way to comfort your child. Sometimes people who don't have children, and even some grandparents who haven't had a baby in a while, try to "make the baby happy" by making silly faces and noises, or otherwise overstimulating him, which can have the opposite of the intended effect. Make sure they are comforting him the same way you would.