If both of those plots are played, can the person still put the 2 cards into shadows? And if so, does that mean they do not count against the 1 card for Fear of Winter (like normal shadows cards do)? Or are they limited to just playing the 1 card into shadows, and are then at the FoW quota?

And is timing a factor here?

Timing is not a factor. Fear of Winter is a constant effect, so it doesn't matter who is First Player. It will always be active when the "When Revealed..." plots are being resolved.

From the FAQ:

(v1.4) Fear of Winter F40
Playing or putting a card into Shadows from
your hand does count against the limitation
set by Fear of Winter. Bringing a card out of
Shadows does not count against this card's
limitation. Replacement effects that put a card
into play from a player's hand (such as those
on PotS Darkstar and PotS House Dayne
Reserves) also count against the limitation set
by this card.

Since putting a card into Shadows from your hand does count against the limit - and because Fear of Winter uses the word "cannot" and is therefore absolute - you would only be able to put one card into Shadows when resolving City of Lies. And that would be it for the round.

Thanks, ktom.