on you Vs with you

Yes you heard it right. When someone asks if you have something on you it is the same meaning as asking if you have something with you. When saying on you it means you are talking about something small enough to be carried on your person.
E.g. "Do you have a pen on you ?"
but "Do you have a towel with you ?"

You did not hear it wrong. And there is no real rule. "on you" is much more informal and, as stated above, usually used with small things. The example with "a Bible" borders on the anomalous, the Bible being a rather large book (unless it's a pocket version of some kind). I would not use "on you" at all, to be honest -- certainly not with anyone like my boss at work; to me it implies so

"Do you have a pen on you?" is poor English. It's an informal attempt at communication, and while we understand what is meant, it's not well said. "What are you gonna do?" is also a question understood, but poor English. Better to ask "Do you have a pen?" or "Do you have a pen I may borrow?".