I play Timely Aid. Gandalf is the ally I choose to play. Do I shuffle the other cards into the deck before I choose Gandalf's response? (Really only an issue if I choose to draw three cards.)

I think yes because the game has no stack.

"Action: Reveal the top 5 cards of your deck and put 1 revealed ally into play, if able. Shuffle all other revealed cards back into your deck. "

You choose Gandalf, put it into play. Now you have to make his response and after that you shuffle back tour deck.