Такие исторические названия указов, как Указ о престолонаследии, Указ о вольности дворянства и т. п., не заключаются в кавычки, первое слово (Указ) пишется с прописной буквы: В 1722 г. Петр I издал Указ о престолонаследии, по которому император сам назначал себе наследника...
Если речь об историческом термине, то править его не нужно.
В § 125 п. 2 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина отмечается: пишутся слитно названия с первыми частями Старо-, Верхне-, Нижне-, Средне-, Ближне-, Дальне-, а также Бело-, Красно-, Черно- и т. п., напр.: Старобельск, Верхнетуринск, Нижнеангарск, Дальнереченск, Белоостров (поселок), Красноуральск, Черноисточинск.
Конечно, может быть традиция, связанная с конкретными названиями, но «при выявлении несоответствия написания конкретного объекта общему правилу в целях сохранения системности нашего письма, единства норм для всех областей русскоязычного мира следует приводить это написание в соответствие с правилами. И только написания названий общезначимых, широко известных объектов, входящих в общий русскоязычный культурный фонд (например, Чёрная речка в Санкт-Петербурге), следует сохранять в их исторически устоявшемся виде».
В данном случае слова «император Александр» зависят от слова «память» и стоят в форме родительного падежа: памяти (чьей?) императора Александра I.
В свою очередь именно слово «память» стоит в форме дательного падежа (как слова «Кузьме Минину и гражданину Пожарскому» во втором примере).
Таким образом, надпись составлена верно.
Можно поставить либо тире, либо запятую. Решать Вам.
Слова Казань, Москва, Новгород, Кострома относятся к разным склонениям. О склонении существительных читайте в пособии Е. И. Литневской.
Ваши наблюдения абсолютно верны. Двоеточие в некоторых случаях может заменяться на тире. И это оговорено в правилах пунктуации. Например, вот примечание к правилу о бессоюзном сложном предложении.
В бессоюзном сложном предложении при обозначении пояснения, причины, обоснования, изъяснения допустимо употребление тире вместо двоеточия (особенно в художественной литературе и в публицистике). Вот, в частности, примеры из произведений К. Паустовского: Изредка в небе светилось голубоватое пятно — за тучками пробивалась луна, но тотчас гасла; Подснежники, наверное, уже прорастали в земле — их слабый травянистый запах просачивался сквозь снег; Слой облаков был очень тонок — сквозь него просвечивало солнце; На молу погасили огни — теплоход ушел; Татьяна Андреевна вздрагивала от сырости — после теплой каюты на палубе было свежо; Паханов крепко держал капитана за локоть — капитан был еще слаб после ранения; Ей хотелось заплакать — лом даже через варежки леденил руки; В армию меня тоже не берут — сердце заштопанное; Однажды зимой вышел я и слышу — стонет кто-то за оградой. (Правила русской орфографии и пунктуации. Полный академический справочник / под ред. В. В. Лопатина. М., 2006. § 129.)
Обратите внимание: такая замена признается допустимой, не ошибочной, но все же в приведенных случаях предпочтительно ставить двоеточие.
Вот примечание к правилу об однородных членах с обобщающим словом.
Допустимо используемое в современной практике печати при всех позициях обобщающих слов употребление тире, в том числе — перед перечислением (на месте традиционного двоеточия): Хороших байдарочников было всего трое — Игорь, Шуляев, Коля Корякин и, разумеется, сам Андрей Михайлович (Тендр.); Если бы его что-то выделяло среди других — талант, ум, красота... Но ничего такого у Дюка действительно не было (Ток.); Всё, всё услышал я — и трав вечерних пенье, и речь воды, и камня мертвый крик (Забол.); Я имел случай и счастье знать многих старших поэтов, живших в Москве, — Брюсова, Андрея Белого, Ходасевича, Вячеслава Иванова, Балтрушайтиса (Б. Паст.). (Правила русской орфографии и пунктуации. Полный академический справочник / под ред. В. В. Лопатина. М., 2006. § 36.)
