O melhor índice para sua consulta é um índice composto em (country, state, latitude, longitude) (country e state pode ser trocado). O MySQL tem uma boa documentação sobre índices de várias colunas, que é aqui .

Basicamente, latitude e longitude não são particularmente seletivos individualmente. Infelizmente, o índice de árvore B padrão suporta apenas uma desigualdade e sua consulta tem duas.

Na verdade, se você deseja processamento GIS, deve usar uma extensão espacial para o MySQL.