He told us to contact the travel agent and book whichever flight ticket was cheapest.
1) First of all, Is the sentence grammatical? -- Yes. Shouldn't the part be 'whichever flight ticket that was the cheapest' ?-- No. 'Whichever' = 'which' and 'which' = 'that'. So your options are:
...book whichever flight ticket was cheapest. ...book t