In the early 1500s (and much earlier, they claim), St. John's was a seasonal fishing station used primarily by the Portuguese, named São João. St. John's is just the translation of that name - lots of myths have risen up crediting various English-speaking sources. None are accurate.
Newfoundland... no idea.
Brigus is my favourite in Newfoundland. It was Brickhouse, and just slowly became Brigus over the centuries.