Que bacana! Eu nunca tive essa visão de desempenho, alias, sempre achei a busca lenta e por isso preferi não usar. Mas a API do BrasilAPI realmente parece ser mais completa.
Nos sistemas que usei normalmente colocava um select de UF e outro texto aberto para cidade rs (nada crítico), eu sei que tem lugares que realmente precisam ser algo relacional.