Faz o que o Rebert falou, ou salvar o lat long do centro da cidade na base, ou o poligono da cidade, acho que não é necessário salvar o poligono pelo fato de ser grande,
E depois você cria um buffer de X km do Lat/Long que você quer,
e depois é só usar o contains para verificar quais cidades estão dentro desse buffer,
Como você não vai usar banco com extensão GIS, usa o GDAL,
ele tem implementações para Java, Python etc....
faz tempo que não trabalho com GIS, mas o caminho é esse se você não quiser usar a API da Google.
Abs