- объявить словарь букв в виде массива (можно взять из таблицы по колонке letter, чтобы лишние не перебирать которых нет в БД)
- пройтись foreach по словарю назначая переменной $letter значение буквы
- в этом же foreach делать запросы на каждую букву SELECT name FROM city WHERE Letter = $letter.
- кидать результаты в некий массив
- перебрать результирующий массив выводя города по группам
Да, запросов будет дохрена (столько сколько разных букв в колонке letter), но с другой стороны у тебя же только в одном месте будет эта портянка городов.
Daria Motorina, можно вообще это делать в админке при добавлении города, сохранять результирующий массив и потом одним запросом юзеру выводить, типа "кэш" такой.