In pasuk ל"א:ח, Moshe gives Yehoshua words of encouragement upon his taking over of Moshe's position. The pasuk ends off, לא תירא ולא תיחת. In pasuk א:כ"א, Moshe commands B'nei Yisroel, with regards to their seemingly imminent conquer of Eretz Yisroel, אל תירא ואל תיחת. The commands are almost exactly identical. The only difference is the exchange of the word אל for the word לא.
Both לא and אל may both be translated as "don't." However, there is a difference between the two. The word אל is, for the most part, confined to a single meaning. Alternatively, the word לא is slightly more flexible. It can take on the form of a command, as in לא תרצח, thou shall not murder. However, it can also take on the form of a promise or assurance. Perhaps the clearest example of this is when HaShem commands Moshe to prevent בני ישראל from ascending the mountain to fight following the incident with the spies. Moshe is told (א:מ"ב) to declare "לא תעלו." The simple reading is clearly, "do not go up!" However, Rashi quotes from a Midrash, "לא עליה תהא לכם אלא ירידה," it will not be an ascent for you, rather a descent i.e. you will not succeed. Here we see clearly that the word לא can mean both a command and a promise, even at the same time.
Therefore, in our parsha, Yehoshua is not being commanded not to fear, but rather being promised that he will have nothing to fear. In דברים, he is being told not to fear. Indeed, the expression in דברים is said in the context of other commands. In our parsha, however, it is stated in the context of other promises.
I understand that the above distinction is not 100% clear-cut and there are numerous examples which might throw it into question. I'm open to suggestions.
Recently, I heard a different approach from משך חכמה. In the פרשה of קרבן פסח - שמות י"ב:ט he explains that אל implies a certain tone of בקשה whereas לא is a more definite prohibitive commandment. Perhaps that explanation can be applied here as well. As leader of the nation it was imperative that יהושע show absolutely no fear whatsoever. Therefore it was delivered in the form of a commandment - לא תירא ולא תיחת. But when בני ישראל are being briefed prior to their imminent entry into ארץ ישראל it is simply stated in the form of a request. Or, alternatively, we can suggest that this "request" was made just prior to the demand for spies which had drastic consequences. With that now many decades in the past but its lessons still very clear, a mere request was no longer appropriate. It was clear that the to not fear and not tremble must be an outright commandment.
