First of all you may know that this hadith appears in several sources with a slight difference in the wording. The version that appears in Sahih al-Bukhari is certainly among the shortest one beside this version there are a short version and a longer version in Sahih Muslim and another long version in Sunan ibn Majah and you may further find other version in other hadith compilations such as Musnad Ahmad, Mosannaf ibn abi Shaybah and al-Bayahaqi's as-Sunan al-Kubra all these narrations are reported on the authority of abu Sa'id al-Khudry.
To be honest -and after a certain research- I must say that this hadith certainly has a lot more open questions than those you've asked and we should be aware that assuming it is authentic (and some may say as it is in the both sahih it must be authentic. Note that this is the only hadith of abu as-Sidiq an-Naji أبو الصّديق الناجي the tabi'i who heard it from abu Sa'id in Sahih al-Bukhari, even if this narrator is qualified as trustworthy by abu Hathim and others while ibn Sa'ad apparently said otherwise without giving a proof as ibn Hajar explained) we should have in mind that the main goal of this narration is to show that we should never despair of the mercy of our Creator and we should and can seek it even if we have wronged ourselves to a level that there seem there's no way out. So on the whole I do assume that it might be understood as a metaphor no more nor less.
On the repentance
Some of these versions actually make clear that this man had the intention to repent:
Abu Sa'id al-Khudri reported Allah's Messenger (ﷺ) as saying that a man killed ninety-nine persons and then he began to make an inquiry whether there was any way left for him for repentance. ... (Sahih Muslim)
'A man killed ninety-nine people, then the idea of repentance occurred to him. ...(Sunan ibn Majah)
The version of imam al-Bukhari actually indicates the same, but doesn't clearly say so.
You may also find indication of him stopping the sin and firmly resolving to never return to it, after consulting the scholar:
...“Woe to you, what is stopping you from repenting? Leave the evil town where you are living and go to a good town, such and such town and worship your Lord there.” So he went out, heading for the good town, but death came to him on the road. … (Sunan ibn Majah)
… He said: Yes; what stands between you and the repentance? You better go to such and such land; there are people devoted to prayer and worship and you also worship along with them and do not come to the land of yours since it was an evil land (for you). So he went away and he had hardly covered half the distance when death came to him and there was a dispute between the angels of mercy and the angels of punishment… (Sahih Muslim)
… He kept on asking till a man advised to go to such and such village. (So he left for it) but death overtook him on the way. While dying, he turned his chest towards that village (where he had hoped his repentance would be accepted), … (Sahih al-Bukhari)
Leaving an environment where one commits sins (i.e. a bar or place where there's mixing of genders or bad company) is also part of the procedure of leaving a sin and stopping it. While going to a pious place (i.e. a mosque) is certainly better for a sincere repentance. Why should he leave because this place reminds him of his former sin or crime and maybe he might have a fall back because the means of re-committing it can be found there. And as long as his repentance is fresh and his faith weak such a fall back is more likely.
If you now said the second scholar himself lived in this "bad environment" I need to say that this is actually not excluded, but it rather seems that he was referring to the questioners environment (as this man travelled two times seeking advice, and apparently he didn't kill anybody after the first wise man) and even if this scholar was living in such an environment he was not the person who committed (such) sins, therefore he might have considered is as his duty to try to advise people and remember them of Allah.
Finally note that this man was searching for advice or a way out of his former crimes, he asked two wise (knowledgeable) people or scholars on whether there's something he might do to be forgiven from what he has done. Therefore I think it is more correct to say the second scholar or wise man "recommended" him than to say he "ordered" him. As after giving advice it is up to the questioner to follow the advice or recommendation or leave it. It was certainly better for him to follow it and that is actually what he has done. This is what I understand as the "range of free will" humans have (accepting or rejecting a good advice). And as I have often explained a fatwa is by no means a verdict that must be followed as it comes from a mufti not a qadi who has been given the power -by the Muslim ruler- to check whether his verdict was applied or not. Finally the scholars interpreted the two towns as the town in which this man used to do his sin (kill) or that in which he killed the monk (first wise man) and the town in which he was to worship and repent.
On the dispute of the angels
The narrations differ when it comes to what exactly happens between the angels:
Some say Allah ordered them to measure the distance:
... Allah ordered the village (towards which he was going) to come closer to him, and ordered the village (whence he had come), to go far away, and then He ordered the angels to measure the distances between his body and the two villages. So he was found to be one span closer to the village (he was going to)…. (Sahih al-Bukhari)
Others say that an angel was chosen as an arbiter and he proposed this solution.
...Then there came another angel in the form of a human being in order to decide between them. He said: You measure the land to which he has drawn near. They measured it and found him nearer to the land where he intended to go (the land of piety), and so the angels of mercy took possession of it.... (Sahih Muslim)
Others say that Allah sent an angel in a human form to act as an arbiter between the disputing angels.
...'So Allah (SWT) sent an angel to whom they referred (the case). He said: “Look and see which of the two towns was he closer, and put him with its people.” (One of the narrators) Qatadah said: “Hasan narrated to us: 'When death came to him he strove and drew closer to the good town, and farther away from the evil town, so they put him with the people of the good town.” (Sunan ibn Majah)
Note that the version of ibn Majah doesn't include the measurement -in first place- and presents the situation as a dispute between the angels of mercy and the angels of punishment in which Iblees interfered. Before adding an addition from another tradition via Humaid at-Tawil that includes the measurement.
The logic behind the measurement solution might be as simple as this: There are angels who say this person has not done any good deed in his whole life and there are angels who say yes, but he repented and his repentance was sincere. Here both argumentations are of "different" kinds. But the solution is of the same kind: "a measurable distance".
What does this hadith teaches us?
Scholars such ibn Hajar al-'Asqalani in his Fath al-Bari فتح الباري see here -in Arabic-, imam an-Nawawi in his al-Minhaj المنهاج see here -in Arabic- and Mulla 'Ali al-Qari in his Mirqaat al-Mafateeh مرقاة المفاتيح see here -in Arabic- concluded the following lessons:
- A scholar is better than a monk or a pious worshiper. Because the scholar actually could help him (note that the version of ibn Majah says that the hundredth man was also among the most knowledgeable people on earth).
- The hadith is an invitation and an awakening of interest for repentance and a call to fight despair one could say a prohibition to fall in despair. As it shows how one could understand:
Say, "O My servants who have transgressed against themselves [by sinning], do not despair of the mercy of Allah . Indeed, Allah forgives all sins. Indeed, it is He who is the Forgiving, the Merciful." (39:53)
- It shows that the (good) intention of a (true) believer (could) have a higher value than his deeds. As the man truly intended to repent and was (actively) looking for a way out of his former misdeeds and transgression.
- It shows (for this we need to go deeper in the commentaries) that the rights of humans don't get dropped by repentance unless these people forgive them or one gets free of them (by punishment or payment for example). Here the Interpretation of the hadith is that the monk or the hundredth victim was either too frightened, ignoring or rejecting the idea that ninety nine victims would even consider forgiving a sincerely repenting murder. And therefore told him something which is only in Allah's hands by rejecting the idea that there's a repentance for him (that might be accepted) which simply goes against the verse I've quoted earlier and the sahih hadith saying:
Allah's Messenger (ﷺ) said to us while we were in a gathering, "Give me the oath (Pledge of allegiance for:
(1) Not to join anything in worship along with Allah,
(2) Not to steal,
(3) Not to commit illegal sexual intercourse,
(4) Not to kill your children,
(5) Not to accuse an innocent person (to spread such an accusation among people),
(6) Not to be disobedient (when ordered) to do good deeds.
The Prophet (ﷺ) added: Whoever amongst you fulfill his pledge, his reward will be with Allah, and whoever commits any of those sins and receives the legal punishment in this world for that sin, then that punishment will be an expiation for that sin, and whoever commits any of those sins and Allah does not expose him, then it is up to Allah if He wishes He will punish him or if He wishes, He will forgive him." So we gave the Pledge for that.
- The hadith shows that tawaba (repentance) can be done for any sin even it would be a major sin like killing (even if it was willful and by purpose).
- It also shows (according ibn Hajar) that Allah will vouch for a killer if He accepted his repentance.
- This hadith also shows that it is highly recommended to leave bad and sinful places and seek refuge in a good and pious environment. As this basically was the recommendation given by the second wise man or scholar. Therefore it is sometimes recommended if not necessary for a person who repents from his former misdeeds to leave certain places to be able to sincerely repent.
- It also shows that a scholar may be wrong or erroneous in his verdict. As it was the case with the first wise man or scholar who ended as the hundredth victim. Ibn Hajar even rejected the idea that the first wise man was ignorant, in fear or simply a monk who was not able to give a verdict.
- It finally shows that the angel scribes which write the records of our deeds may dispute based on their own Ijtihad on whether the person is a sinner or a pious person and that they seek Allah's final verdict in such cases.