Для реализации js может пригодиться
autocomplete или, если используется бутсреп,
typeahead.
А для серверной части — да, только ФИАС парсить и в базу. Какого-то вменяемого api несколько месяцев назад так и не нашел даже для городов, не то что для улиц/домов. 2ГИС и Яндекс, судя по всему, для поиска и автодополнения пользуются своими гео-базами, так что надеяться на них чрезмерно не стоит.
