Vous avez écrit :
je vais à Paris » : mes certitudes ont disparu… même si je comprends aujourd’hui qu’il s’agit d’un COI.

On avait dit « complément de lieu » essentiel et non circonstanciel, même si cette dénomination peut être un peu baroque.

Où es-tu ? : où est un pronom interrogatif dans cette phrase (mais aussi pronom relatif dans d’autres structures).

Nous viendrons à Noël : complément essentiel de temps

Pour rappel : 
On dit qu’un complément est essentiel quand il dépend du verbe lui-même et que – sans lui – le verbe ne peut avoir un sens. Certains compléments circonstanciels peuvent être essentiels. Cette nuit, il a neigé. La séance de cinéma dure deux heures.

etc.

Attention de ne pas tout mélanger.
Ce type de confusion, qu’on observe de plus en plus, vient du mélange dans l’approche de la langue de deux méthodologies » différentes. On vous parle de CC et de complément essentiel, on vous propose de supprimer tel ou tel élément. Hou là là !
La grammaire traditionnelle connaît les notions de CC, COI, COD
La linguistique partage les compléments entre essentiels et non essentiel et ne parle pas de la différence CC/CI par exemple.
On a là deux approches différentes qui sont souvent mélangées dans les manuels scolaires, même ceux qui sont réputés bons.
—-
Choisissons la première approche qui a été utilisée depuis plusieurs générations et qui donc est la plus abordable.
Le COD, COI et CC sont des compléments du verbe.
Le COD : complément d’objet direct : son nom a du sens : il désigne l’objet sur lequel porte l’action et il est construit directement après le verbe, c’est à dire sans préposition : je mange un fruit.
Le COI désigne un objet sur lequel porte l’action mais il est construit indirectement, c’est à dire qu’entre lui et le verbe il y a une préposition : Je parle à mon oncle – je parle de mon oncle
Le CC , complément circonstanciel, donne une des circonstances de l’action portée par le verbe : pour l’avoir, on pose les questions où, quand, comment, pour quel  but, pourquoi, avec qui , avec quoi..… ? (voir le sens du mot « circonstance » : ce qui entoure (ici, l’événement ou le fait dit par le verbe)
souvent le CC est introduit auprès du verbe par une préposition : j’ai mis l’assiette sur la table. Mais pas toujours : il fait une petite promenade le soir.
>>> le COD ne se déplace jamais sauf avec une formule d’insistance : c’est un fruit que je mange mais jamais un fruit je mange
>>> le COI  : même chose
>>> le CC peut souvent se déplacer  : le soir il sort/il sort le soir – sur la table il y a une assiette/il y a une assiette sur la table
Si on l’enlève, ce qui reste garde du sens : il sort – il y a une assiette
Il ne se déplace pas quand le verbe ne peut pas s’en passer. en ce cas on ne peut employer le verbe sans un CC  : il va à Lyon mais pas à Lyon il va ni il va (tout seul)  >> (en ce cas la linguistique parle de complément essentiel)

—
Les interrogatifs : ce sont des adverbes :
où : adverbe interrogatif de lieu : la réponse sera un CC de lieu
quand : adverbe interrogatif de temps : la réponse sera un CC de temps
pourquoi : adverbe interrogatif de cause : la réponse sera un CC de cause
etc.

Désolée, difficile  de faire plus court.

— Dans votre phrase, où est un complément essentiel (de lieu ou encore locatif)) du verbe être.
(source)

Il est dans la cuisine ; dans la cuisine = complément essentiel (de lieu) du verbe être.

— Dans votre phrase, venir est intransitif, il signifie (extrait de Usito) :

À Noël, n’est pas nécessaire à la réalisation du procès venir, ce complément indique donc une circonstance de ce procès.

Vous verrez dans le dictionnaire que j’ai cité (Usito) que dans d’autres cas venir peut être transitif indirect, que par conséquent le complément qui l’accompagne n’est plus circonstanciel, mais essentiel (catégorisé COI par certains). Par exemple :

Nous viendrons chez vous à Noël.
Je viens de Paris, et je vais à Londres.

Pour vos interrogations concernant la nature des compléments, je vous conseille de vous référer à ce dictionnaire, puisqu’il prend en compte la nouvelle grammaire dans la description des verbes (tout en indiquant la classification retenue par la grammaire traditionnelle).

Il existe un test (mais qui comme tous les tests de genre connait des limites) pour voir si un complément est essentiel ou non  : l’insertion de « et cela » :
Il est, et cela dans la cuisine >>> incorrect : complément essentiel.
Nous viendrons, et cela à Noël >>> correct : complément circonstanciel.
Nous viendrons, et cela chez vous / et cela de Paris >>> incorrect : compléments essentiels.