The same applies to the environment with fitness being non-random.
What he meant (I think) is that mutations are biased towards conservative amino acid changes, that is changes towards amino acids that are more like the original amino acid. However, there is no specificity with respect to the environment or the specific genetic locus. It is very much like 7 being more common than 2 or 12 in craps.
As you state, this only increases the mutation rate in genes, and those mutations occur whether they are neutral, beneficial, or detrimental. As an analogy, this is like poor people buying more lottery tickets than rich people. Even though this trend exists the lottery is still random.
A scenario I would consider non-random would be a membrane bound protein that sensed antibiotics and then triggered other enzymes to make a specific mutation in a specific gene to produce antibiotic resistance.