1) Прежде чем они добрались до города, им навстречу УЖЕ бежали
люди...
По-моему, здесь УЖЕ по своему значению стоит ближе к наречию с временным значением, чем к частице.
2) Хотя дождь шел всю ночь, в лесу было УЖЕ сухо.
То же и здесь: наречие. Ср.: Хотя дождь шел всю ночь, в лесу СЕЙЧАС было сухо.
3) ОТТОГО, быть может, ЧТО в глазах мелькали деревья..., САМЫЕ
разнообразные мысли приходили ей в голову.
ОТТОГО находится в главной части СПП, является соотносительным словом -- местоименным наречием.
3) …САМЫЕ разнообразные…
Здесь САМЫЕ -- частица, имеющая усилительное значение.
4) У заборов были деревья, бросавшие теперь при солнце широкую тень,
ТАК ЧТО заборы и ворота… утопали в потемках...
ТАК ЧТО = поэтому, вследствие чего. Союз. См. http://dic.academic.ru/dic.nsf/efremova/252585
4) …заборы и ворота на ОДНОЙ стороне совершенно утопали в потемках...
Прилагательное.
ДОПОЛНЕНИЕ
В ответе Vera прозвучало, что "Здесь САМЫЕ -- местоименное прилагательное… У частицы значение соответствия действительности (на самом деле)".
Опровергать возможность называния слова "самый" в сочетании с прилагательными местоименным прилагательным я не буду. ГОСТов на термины нет, лингвистов у нас много, каждый вправе пользоваться своей терминологией.
Приведу только несколько слов из книги Бабайцевой В.В. "Явления переходности в грамматике русского языка":
В учебниках и учебных пособиях слово самый обычно включается в
разряд определительных местоимений, хотя во многих работах показано,
что в современном русском языке нет местоимения самый.
Наиболее очевидна квалификация слова самый как
формообразовательной частицы в сочетании с прилагательными для
выражения значения превосходной степени: Да приснятся тебе самые
лучшие, самые красивые сны (А. Чехов); Калиныч был человек самого
кроткого, самого весёлого нрава (И. Тургенев); Всем известно, что
сорока -- самая болтливая птица (К. Паустовский)...