В этом заголовке слово путешествуя совершенно точно является деепричастием: оно называет дополнительное действие по отношению к основному действию, названному глаголом жить. При этом есть правило, согласно которому деепричастный оборот не обособляется, если он тесно связан по содержанию со сказуемым и образует смысловой центр высказывания, например: Жили Артамоновы ни с кем не знакомясь (М. Г.), Старик шёл прихрамывая на правую ногу и т.  п. Однако заголовок Жить (,) путешествуя не представляет собой предложения, и оценить, образует ли деепричастие смысловой центр высказывания, здесь едва ли возможно. Это аргумент в пользу постановки запятой. Сравним пример предложения, в котором деепричастие играет особую коммуникативную роль и не обособляется: Это здорово — жить путешествуя!

В первой части предложения сравнительный оборот образует смысловой центр (смысл не в том, что полицмейстер заходит в лавки, а в том, как именно он это делает), а значит, тесно связан со сказуемым, что дает основание не обособлять его. Сравним примеры из Национального корпуса русского языка: Художники и гуманисты приходили к Козимо как к себе домой и чувствовали себя с ним совсем просто. [А. К. Дживелегов. Вазари и Италия (1933)] (здесь случай, подобный Вашему); А то я туда сунулся, как к себе домой, а там мужик какой-то незнакомый [А. Маринина. Не мешайте палачу (1996)] (смысловой центр первой части, важный для развития сюжета, образует сказуемое сунулся, оборот как к себе домой добавляет малосущественную характеристику).

Это предложение построено некорректно вне зависимости от того, слитно писать небольшая или раздельно. Союз а используется для противопоставления (и не равен по значению союзу но). При этом слова большой и интересный не могут противопоставляться друг другу.

Вы правы. Правильно здесь: где бы не побывал путешественник.  

В таком случае наименование следует склонять: органом ЗАГС Москвы № 127 Многофункциональным центром предоставления государственных услуг.

В русском языке аббревиатуры и несклоняемые существительные иноязычного происхождения (не обозначающие живых существ, то есть неодушевленные, ср. слова на -и: сулугуни, салями, кольраби, цукини) обычно приобретают те родовые признаки, какими обладают опорные слова. В случае с аббревиатурами эта закономерность проявляет себя наиболее последовательно. Нагляден пример аббревиатур, образованных на базе сочетаний со словом институт (НИИ, МАИ, ИАИ и т. д.), центр (НЦБИ — научный центр биологической информации): они употребляются как существительные мужского рода. Иноязычные аббревиатуры не исключение: Би-би-си — существительное женского рода (по слову корпорация); у существительного среднего рода ЦРУ есть опора в виде существительного управление; существительное мужского рода сиди (от СD) наследует грамматические признаки слова диск. В печатных изданиях можно встретить обороты типа базовый / функциональный / мощный / удобный API. Они свидетельствуют о том, что иноязычная аббревиатура API (с опорой в виде слова интерфейс; от англ. Application programming interface) согласуется с прилагательными по образцу существительного мужского рода. Вместе с тем констатируем: в текстах запечатлены и сочетания, в которых аббревиатура API предстает как существительное среднего рода; ср. мощное и удобное API.

Приведенное Вами название нежелательно использовать без родового слова. При родовом слове обе части не склоняются.