Хранить список городов в бд или использовать сервисы?

В любом случае нужно хранить у себя. Это даже не подлежит обсуждению. Чтобы ваш сервис не перестал работать, образно говоря, из-за того, что где-нибудь на другом конце мира уборщица шваброй задела провод. Но как вы правильно заметили, встает другая проблема - актуальность данных. А её решить достаточно просто. Забирайте данные из стороннего api периодически и обновляйте данные у себя в базе. Как часто это делать, и каким образом, полностью заменять локальные данные/подтягивать только обновления и т.д.? - Зависит от объема данных, природы этих данных и пр. В случае списка городов наверное можно автоматический апдейт делать раз в месяц или даже раз в квартал, или даже раз год. Не так часто появляются/исчезают/переименовываются города. И по необходимости можно запустить обновление вручную.
Если вы не последуете этому совету и решите запуститься без локальной копии. То в скором времени вам всё равно придется переделывать. Потому что в реальном мире сети рвутся, сервера падают, фаерволы режут трафик, а сервисы внезапно перестают отвечать на запросы.