Cita: La consulta que quiero hacer a la BD es que me ordene por un número de coincidencias, es decir, cuántos usuarios son de la misma ciudad y que me los ordene. Estaría bien hacer el índice al campo ciudades?
Es básicamente innecesario, porque tanto los agrupamientos como el ordenamiento consumirán más tiempo que lo que el índice puede acelerar la consulta. Además, de todos modos la consulta en cuestión deberá leer toda la tabla de usuarios para realizar la tarea, con lo que en realidad serán muchos más los recursos usados por eso que lo que el índice te puede aportar.
En el contexto de tu caso, un índice se justificaría a partir de tener centenares de miles o millones de registros. Si tan sólo tendrás algunos miles, no notarás una diferencia apreciable.
Además, un índice es una tabla que el sistema debe mantener actualizada, por lo que lo que se verá afectado es la performance de los INSERTs.
Una de las reglas de la optimización de consultas (y de las bases) es precisamente no crear más índices que los realmente necesarios.
Prueba ambas situaciones y analízalas con EXPLAIN. De allí verás si realmente es necesario.