A level 1 player character is assumed to have taken on at least 1 somewhat notable quest or mission. That's why they are level 1 and not a pissant peasant with virtually no stats. You might not be known world wide, and you wouldn't have saved the world or anything grandiose as that; but maybe your fighter was a city guard and known to have stomped out some bandit camps in the region or helped hold back the advance of a goblin horde.

With the players themselves having these rumors, they're already in the same area to have met each other so why wouldn't they have possibly heard about some of the deeds the rest of the party may have had before they met?

New in town doesn't mean unheard of. You could build up a reputation on the way to town that is being passed around by other travelers.

And some if the rumors could be things that happened the night before.