Il y a quelques siècles, on disait « la ville où Charlemagne est mort » et « le jour que Charlemagne est mort ». Les deux pronoms relatifs étaient différents.
— Depuis le jour que je le perdis, je ne fais que traîner languissant (Montaigne)
Mais de nos jours, le relatif « où » sert à la fois pour l’espace et pour le temps, pour désigner un lieu ou un moment.
— Dans la ville où je vous ai rencontrée…
— Depuis le jour où je vous ai rencontrée…
Il est possible qu’il subsiste en français des « que » dans des expressions, dans des variantes régionales, dans certaines classes sociales, ou par goût des formes classiques, mais pas dans la langue standardisée.
Quand un poète écrit : « le jour que je vous vis », c’est un effet de style recherché et élégant.
Quand un ouvrier dit : « le jour que je vous ai vue », c’est un usage populaire et inélégant.
On tire de cette comparaison des usages actuels les conclusions politiques qu’on souhaite en tirer.

Avec le mot « fois » à la place du mot « jour », c’est différent, et il peut y avoir une nuance immense, car « une fois » peut être une occurrence comme une indication de temps.
Comme occurrence, on utilise obligatoirement « que », tandis que comme indication de temps, le « où » est préférable, avec la tolérance d’usage développée ci-dessus.
a) Occurrence :
— Pour une fois que tu venais, il pleuvait.
b) Indication de temps :
— Rappelle-toi la fois où tu est venu, il pleuvait.
Il est possible que les deux se mélangent ou se superposent dans l’usage, mais la distinction ci-dessus est cependant nette.
c) Tolérance :
Pour une indication de temps, bien que l’usage moderne standardisé demande le pronom « où », la forme en « que » est possible :
— Une fois que la princesse cueillait des fleurs, une grenouille lui dit…
C’est un style, soit vieux et conforme aux usages pour un conteur, soit recherché pour un écrivain, soit populaire pour un ouvrier, et il existe donc plusieurs raisons d’accepter cette phrase.
En revanche, quand c’est le « que » qui est nécessaire pour cause d’occurrence, il n’est pas possible d’utiliser le « où » qui dénoterait non pas une tournure élégante mais une interprétation fautive de l’esprit de la langue française.
— Je suis au courant de son insistance et des deux fois où il est venu (il faudrait écrire : les deux fois qu’il est venu).

Avec « la première fois », le sens indique a priori qu’il s’agit de l’occurrence :
— C’était la première fois que je vous voyais…
— La première fois que je vous ai vue, vous m’avez dit que…
L’indication de temps est cependant possible, avec une utilisation assez pauvre du mot « fois » :
— La première fois où je vous ai parlé, je m’en souviendrai toujours, vous portiez un chapeau gris…
Dans ce dernier cas, un autre mot que « fois » serait le bienvenu :
— La première soirée où je vous ai parlé, je m’en souviendrai toujours, vous portiez un chapeau gris…

Avec votre exemple, je terminerais vos phrases ainsi.
Occurrence :
— La première fois que je l’ai rencontré, c’était à l’initiative d’un ami commun.
Indication de temps :
— La première fois où je l’ai rencontré, c’était un samedi pluvieux.