[-De-]

1. Если нормально сделать, то некритична.
2. По каждому нажатию кнопки отправлять HTTP запрос - плохая идея. Сокет вполне осилит нужную интерактивность (но вообще-то его нужность под вопросом, проблемы с проксями итп.). Может, грузить список после ввода 1-2 символов, лучше сжатый. Однозначно нужен список, вшитый во флешку или загруженный изначально, из городов которого там 90% юзеров будут. Может, грузить что-то только если введённого юзером нет в базовом списке.
3. А сколько у вас городов всего, сколько весит список городов, сколько он весит заархивированный?
А чем текущая реализация-то не устраивает? Тут скорее надо прыгать, а не думать.