Сочетание и да в этом предложении цельное, оно выполняет связующую функцию, «сигнализируя о появлении добавочного суждения, которое носит, как правило, ассоциативный характер» (Шпильман М. В. Некоторые наблюдения над использованием сочетания и да в письменной речи // #ТОТСБОРНИК: Сборник научных трудов по материалам Тотального диктанта. Вып. 4 / Отв. ред. Н. Б. Кошкарёва. — Новосибирск, 2017. — С. 180–185). Между частями сочетания запятая не нужна, а вот после него обычно ставится именно запятая, а не двоеточие: И да, это не просто традиционная усталость, это нечто большее.

Судя по электронному каталогу Российской государственной библиотеки, написание старого названия Новосибирска до переименования не было единообразным: в карточках книг начала ХХ века встречается много и дефисных, и слитных написаний.

Ведущие энциклопедические издания (БСЭ, БРЭ), в которых большое профессиональное внимание уделяли и уделяют орфографии собственных имен, дали старое название города без дефиса — Новониколаевск (см., например, на сайте БРЭ статью Новосибирск и другие статьи). Такую же форму находим в топонимическом словаре Е. М. Поспелова «Географические названия России» (М., 2008).

Таким образом, общая рекомендация — ориентироваться на словарную традицию и писать слитно: Новониколаевск.

Ваш вопрос не вполне понятен, но все же попробуем ответить. Словари, представленные на портале, включают разное количество слов и словарных статей. Так, в «Русском орфографическом словаре» статей больше, чем в других словарях, например в «Большом толковом словаре русского языка». Но, пользуясь словарями, нужно учитывать, что во многих из них не у каждого слова есть своя собственная словарная статья, некоторые слова (или сочетания слов) можно найти в текстах словарных статей других слов. Например, в «Большом толковом словаре русского языка» слово учительница включено в статью учитель, а в «Русском орфографическом словаре» учительница и учитель — две самостоятельные статьи. При этом в «Русском орфографическом словаре» собственное имя часто входит в статью производного от него слова (Ломоносов — в статью ломоносовский, Новосибирск — новосибирский, Лиссабон — лиссабонский, Прудон — прудонизм и проч.), составное название, фразеологизм — в статью одного из входящих в него слов (лог, луна), в одной статье могут сопоставляться два слова, два произносительных варианта слова (эдем, ладаки и ладакхи). При обновлении портала количество словарных статей в словарях не изменилось, а вот словарей стало больше.

Правила постановки знаков препинания при сочетании вводного слова и обособленного оборота изложены в параграфе 93 «Полного академического справочника» под ред. В. В. Лопатина (М., 2006 и след.). В справочниках и специальной литературе не отмечено, что вводные слова разных семантических групп «ведут себя» в таких условиях по-разному. 

Другое дело, что, если вводное слово находится в начале оборота, пишущему действительно хочется как-то выделить и сам оборот, и вводное слово. В этом случае одними только запятыми не обойтись, нужно использовать еще и тире. Такие ситуации подробно проанализированы в статье С. В. Друговейко-Должанской «О корректировке правил пунктуационного оформления вводных конструкций (тире перед вводными словами и словосочетаниями)» (#ТОТСБОРНИК: Сборник научных трудов по материалам Тотального диктанта. Новосибирск, 2017. Вып. 2. С. 132—145).

Очевидно, сочетание без участия заявителя характеризует предоставление услуг? Тогда причастный оборот, относящийся к слову информация, будет таким: необходимой для предоставления государственных услуг без участия заявителя. Внутри него запятая не ставится.