In the dictionary
company: guests in your house
I didn't realize you had company.
However, in several movies, I often hear people say "we have company" or "we've got company" even though that person is just a stranger.
Say I was the only one in a cafe in the early morning and after a while, a person walked into the cafe.
Can I say "We have company"?
In its most literal use, 'company' does tend to mean friendly visitors to your home, or that you have someone with you in another settings - someone you would call a companion.
Saying "I/we have company" can be a way of indicating that you are now in polite company, and 'polite company' is defined as "with people you do not know well", where certain subjects may be inappropriate to talk about. So, 'company' does not always mean people you know. In your scenario of someone entering a cafe, if you are saying it to mean you should now watch the subjects of discussion more closely then that would seem appropriate.
The kind of scenario you are mention in movies where the action hero spots a car following them and says "we got company!" is more of a sarcastic, euphemistic use.
In the scenario you describe, it would be odd to say, “We have company” because you were the only one there. To whom would you say it? The new arrival? Now that would be extremely odd.
If instead of being alone, you were sitting with a companion when the new person arrived, then you could say (to your companion, and about the arrival), “We have company.” But again, that would be remarking on the new arrival, not on the fact that you had already had a companion. On the other hand, if the newcomer was a person with whom you had made an appointment and your companion had been unanticipated (whether an acquaintance or a stranger), then too you could say (but to the expected newcomer , and about the unanticipated companion), “We have company.”
