S>есть устойчивый стереотип что нати работу в Канаде без знакомств очень трудно

Не в Канаде, а везде. Первую работу найти очень сложно. Нужны референсы с предыдущих мест.