С первых же дней новый владыка начал твердой рукой наводить порядок в епархии, опираясь на поддержку великого князя в лице его новгородских наместников. Но в отличие от своего предшественника Геннадий действовал с осторожной твердостью, учитывая, по возможности, местные традиции и стараясь не оскорблять чувства новгородцев. Введя в богослужение молитвы за великого князя, он соблюдал древние новгородские обычаи и по примеру республиканских владык взял на себя постройку третьей части возобновляемой городской стены.
Помимо прочих неурядиц, Геннадий обнаружил в своей епархии различные толки. Верующие спорили, следует ли на всенощной петь: «Аллилуйя, аллилуйя, аллилуйя, слава тебе Боже!» или «Аллилуйя, аллилуйя, слава тебе Боже!» Принимавшие первый способ «трегубили» аллилуйю, а принимавшие второй — «сугубили». Сугубившие опирались на то, будто аллилуйя в переводе значит «Слава тебе Боже», хотя на самом деле аллилуйя означает:
(Вопрос об аллилуйе так и «завис», перейдя в грядущие столетия, чтобы, соединившись с другими разногласиями такого же формального толка, взорваться церковным расколом, которому будет суждено стать величайшей трагедией в истории Русской православной церкви. —
Много хлопот доставил Геннадию Псков. Воспользовавшись длительным безвластием в новгородской епархии, псковичи снова попытались от нее отложиться. Они наотрез отказались пускать в свои храмы новгородских «переписчиков», посланных Геннадием, и не приняли владычного наместника. Подобные попытки Псков предпринимал в прошлом уже не раз. Еще при покойном владыке Ионе возник острый конфликт вокруг вдовых попов, которых псковичи обвинили в сожительстве с наложницами, из-за чего, по мнению прихожан, их молитвы не доходили до Господа. Тем не менее архиепископ Иона оставил вдовых попов на их приходах за дополнительную мзду дому Святой Софии, чем вызвал бурю возмущения псковичей. Зная об агрессивных намерениях Ивана Васильевича в отношении Новгорода, псковские власти решили тогда заручиться его поддержкой, чтобы заполучить собственного владыку. Однако они горько ошиблись в своих расчетах, Иван Васильевич целиком поддержал Иону, а псковичам, словно в издевку, вместо владыки прислал в подарок… верблюда. Этим шагом дальновидный Иван Васильевич нейтрализовал новгородского владыку, и вполне вероятно, что преемник Ионы Феофил вспомнил об этом эпизоде, когда перед битвой на Шелони приказывал своему полку не вступать в сражение с московскими войсками, а биться только с псковичами. После покорения Великого Новгорода, в котором псковичи воевали на стороне великого князя Московского против своего «старшего брата», псковские власти посчитали, что в благодарность за это великий князь теперь-то уж точно поддержит их в конфликте с новым архиепископом. Однако их ожидало новое разочарование. Иван Васильевич всецело поддержал Гонзова, и не только потому, что тот был его назначенцем, но и по принципиальным соображениям, ибо он являлся противником всякого сепаратизма, равно светского и церковного.
Приструнив псковичей, Геннадий впредь постарался не выпускать из поля зрения ненадежный город. Он помнил, что именно здесь зародилась ересь стригольников. Истовые в вере, псковичи были нетерпимы к мздоимству и прочим грехам духовенства, и теперь владыка опасался, что стригольническая ересь может сюда вернуться. Но оказалась, что другая ересь, куда более опасная, свила гнездо буквально под самым его носом. Наткнулся на нее архиепископ Геннадий, можно сказать, случайно.
…С отъездом из Новгорода ересиарха Захарии Скары, а затем и первых «пришельцев врат» Алексея и Дениса, ересь в Новгороде не то чтобы заглохла, а как-то выродилась. Лишившись своих наиболее образованных членов, кружок вольнодумцев постепенно превратился в тайное сборище хулителей традиционного православия и церковных порядков. Дело усугубилось русским пьянством.