When Agent Fury met Vers at the phone-booth for the first time in Captain Marvel, she called him "Agent Fury", but he didn't introduce himself there, right? How did she know his name?
He did introduce himself, actually. Not by saying his name, but by showing his identification. Hence Vers' line:
We don't carry our identification on little cards.
The "little card" contained various info but most importantly here, his name, which is how Vers was able to name him when she said:
Congratulations agent Fury, you finally asked a relevant question.
For the record, here's a picture of Fury's ID, seen later in the movie. His name is partially hidden by the thumb, but this is what Vers saw: