1) Слишком абстрактный вопрос. Если правильно спроектирована БД, есть ключи, связи, то все будет работать быстро. Здесь же зависит многое от конфигурации сервера. Если у вас 1 000 городов в базе и 1 000 000 объявлений, то это не нагрузка вовсе, тем более на том же сайте с объявлениями на букву А, связи один к одному, т.е одно объявление относится к одному городу и вам не нужно будет делать сводную таблицу для этого, достаточно добавить в объявление поле location_id и по нему делать выборку.
2) Есть много видов кэширования. Что именно кэшировать вы решили? Представления? Запросы? В любом случае оно возможно, но вводить его нужно, когда вы уже знаете узкие места в системе.