When does the "choose a color" part of a spell happen?
The ability reads as follows:


  When Sejiri Steppe enters the battlefield, target creature you control gains protection from the color of your choice until end of turn.


The color is chosen when the ability resolves. At that point, there's no chance for anyone to respond. Here's what happens in more detail:


The ability triggers. Its controller chooses a target for the ability.
Both players have a chance to cast spells or activate abilities.
The ability resolves. A color is chosen, and the target gets protection from the chosen color.


Here's a ruling on Feat of Resistance, a card that has similar wording:


  9/20/2014 You choose the color as Feat of Resistance resolves.