Пермь - могу посоветовать г-цу Вояж на Большевисткой 141, телефон 8-912-989-35-05.
Это гостиница "квартирного" типа - просто купили 3-комнатную квартиру в обычном жилом доме и в каждой комнате сделали отдельный "номер".
Цену не вспомню, но дешево вроде было. И это в 5 минутах ходьбы от самого центра города.
Минус - еду надо готовить самостоятельно, есть тока м/в.

Екат - такого же типа гостиница Аквамарин, тел. +7 (343) 251-9297.
Минус - расположена в бывшей общаге какого-то института (или техникума даже), к-й остался стоять на прежнем месте - т.е. рядом. Соответственно, не знаю или мне так повезло, или всегда такое, но под окнами собралась толпа студентов и некоторое время шумела.
Расположение - относительно недалеко от центра.