Обледенелый — отглагольное прилагательное, образованное от обледенеть. В «Правилах русской орфографии и пунктуации» (§ 63) под ред. В. В. Лопатина говорится: «Приобретение какого-нибудь признака, переход в другое состояние выражается также в непереходных глаголах I спряжения на -ене́ть, в которых безударный гласный перед н передается буквой е: леденеть, костенеть, деревенеть, коченеть, травенеть, торфенеть, окровенеть, остекленеть, остервенеть, остолбенеть, оцепенеть». Исключением является глагол багрянеть.

В некоторых иноязычных собственных именах, этнических названиях после ж, ш, ц пишутся буквы я, ю, например: Жямайтская возвышенность, Жюль, Сен-Жюст, Жюрайтис, Шяуляй, Цюрих, Коцюбинский, Цюрупа, Цюй Юань, Цявловский, Цяньцзян, цян (народность). В этих случаях звуки, передаваемые буквами ж, ш, ц, нередко произносятся мягко. См.: Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2006. § 13.

При произнесении названия Цюрих согласный ц смягчается. Произношение [цу]рих неправильно.

Сочетание а значит сигнализирует о логическом выводе, запятая после него нужна (см. параграф 95 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина): ...её габариты — а значит, и размеры заложенных фундаментов — задавала длина строительного бревна... Запятая не будет ставиться, если присоединительную конструкцию обособить запятыми (см. параграф 93 того же справочника): ...её габариты, а значит и размеры заложенных фундаментов, задавала длина строительного бревна...

В подобных контекстах сочетание начиная с играет роль предлога, оборот с ним не требует обособления (см. параграф 73 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина): Следует заметить, что начиная с войны во Вьетнаме на них стремились возложить выполнение разведывательных задач по уничтожению объектов противника. Оборот может быть обособлен «для попутного пояснения или смыслового выделения» (см. параграф 74 того же справочника).

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

Если вводное слово или сочетание слов находится внутри вставной конструкции, то оно выделяется по общему правилу, например: В иных озерах (например, в Черненьком) вода напоминает блестящую тушь (Пауст.). Сравним: В иных озерах, например в Черненьком, вода напоминает блестящую тушь (здесь вводное слово находится в начале присоединительной конструкции и не отделяется от нее запятой). См. параграф 93 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина.

В сочетании г. Пермь Пермской области зависимые слова Пермской области, грамматически связанные с существительным Пермь, играют при нем роль несогласованного определения, называющего постоянный признак (см. параграф 53 «Полного академического справочника» под ред. В. В. Лопатина и приведенный в нем пример табуретки с золочеными ножками).

Во втором приведенном Вами случае сочетание Пермская область грамматически не связано со словом Пермь, оно несет в себе дополнительную информацию, а потому его уместно оформить как вставку в скобках: г. Пермь (Пермская область).

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

А. В. Суперанская, один из лучших специалистов по ономастике, считала, что «номенклатурные термины [родовые понятия] составляют неотъемлемую часть географических названий», однако в своих публикациях она часто пишет о «собственно названиях», отделяя их от родовых слов-понятий. Объединяющим термином у А. В. Суперанской часто выступает слово топоним (см., например: Суперанская А. В. Прописная и строчная буква в собственных именах различных категорий // Орфография собственных имен / отв. ред. А. А. Реформатский; АН СССР, Ин-т рус. языка. М.: Наука, 1965. С. 25–43).

Судя по всему (хотя предложение не приведено полностью), в данном случае есть три однородных члена предложения, перед каждым из которых, кроме первого, повторяется союз или. Если это так, то корректно следующее пунктуационное оформление: ...аттестат об основном общем образовании, или аттестат о среднем общем образовании и приложение к нему, или справку об обучении из организации. Сравним пример из параграфа 13.6 справочника по пунктуации Д. Э. Розенталя: Иные хозяева вырастили уже вишни, или сирень, или жасмин (Ф.).