Eu mantenho todas as cidades no banco de dados. Encontrei um Seeder no github há anos e sempre uso ele. link aqui
Aqui a pergunta é: Porque não manter em banco? É um número pequeno, previsível e que quase nunca muda. Latência de um banco é uma ordem de grandeza menor que a latência de uma API.
Caso Seja uma necessidade extrema é recomendável a api dos correios. porém tem que ter contrato com eles
Qual banco de dados você utiliza?
Sinceramente é irrelevante, qualquer DB vai armazenar isso com eficiência por ser uma quantidade de dados muito pequena.
Atualmente MySQL ou Postgres
Concordo plenamente.