Да, на его поиски является обстоятельством цели, в город Альмерию – обстоятельством места.

Слово город избыточно, лучше обойтись без него: в Москве и Казани (и так понятно, что это города). Если по каким-либо причинам без слова город обойтись нельзя, то корректно: в гг. Москве и Казани.

Употребительна модель столько-то дней (трудной) дороги, где слово дорога имеет значение 'путешествие, поездка'. Однако, полагаем, можно говорить и о днях трудных дорог, то есть о времени, когда пришлось пройти, проехать по множеству непростых для передвижения дорог.

Географические названия среднего рода, оканчивающиеся на -е, -о, обычно не склоняются в сочетании с родовым словом: в городе Яровое (это название не склоняется, т. к. при склонении сложно будет восстановить исходную форму: в городе Яровом – это город Яровой или город Яровое?).

Метрополис (от греч. metrópolis — главный город), 1) крупная городская агломерация, сложившаяся в результате слияния нескольких городов или слияния города с окрестными поселениями (в этом же значении используется и слово мегаполис); 2) центральный город страны или какого-либо крупного подразделения государственной территории.

Это выражение употребляется в значении: мысль, способ и т. п., помогающие разобраться в сложной обстановке, найти выход из какой-либо трудной, запутанной ситуации. Выражение возникло из древнегреческого мифа о Тезее, убившем Минотавра. Дочь критского царя Ариадна дала Тезею клубок ниток, чтобы он мог найти выход из лабиринта.

Речь идет о лексической избыточности (т. е. понятно, что Тула - это город, а май - это месяц, а значит слова месяц и город лишние). В отличие от тавтологии (масло масляное), которая является ошибкой, лексическая избыточность (плеонастичность) возможна в определенных ситуациях (Ваши примеры - из канцелярской, деловой речи).

Слово несколько — местоимение-числительное. Оно обладает грамматическими признаками количественных числительных, в частности особым образом сочетается с существительными: в именительном и винительном падеже — управляет формой родительного падежа множественного числа существительного (несколько домов), в других падежах — согласуется с существительным (нескольких домов, нескольким домам, несколькими домами, в нескольких домах).

В сочетании со словом город слово Олимпия в любом случае является приложением. Правило о склонении названий городов в сочетании со словом город распространяется не только на исконные наименования, но и на давно заимствованные и освоенные. К этой группе и можно отнести слово Олимпия. Поэтому сочетание в городе Олимпии соответствует литературной норме.