[-De-]

Ну типа 2 млн. городов, ну пусть 10 млн. - меньше 30 шагов по бинарному дереву, нормальная организация бд или своё дерево и проблем со временем доступа у сервера нет, но загрузить всё нельзя. Я бы таки сделал вариант - 10к городов вшить/грузить (менее 100 кб), если юзер вводит то, чего нет там (что редко (а может вообще никогда, если он не бред пишет), тогда он подождёт ответа сервака).
Максимально быстро и интерактивно - запрос на сервер слать через сокет, если имеющееся не может предложить n (напр 5) вариантов, сервер отдает не более m*n (m напр 6) новых вариантов.