Eis a lista com o nome das cidades e de onde são capitais [observe-se que os adjectivos não são usados com inicial maiúscula a não ser quando iniciam a frase]:

Aracaju (Sergipe): aracajuano – também se usa aracajuense, mas a primeira forma é preferível.
Belém (Pará): belenense – belemita é o natural de Belém na Cisjordânia.
Belo Horizonte (Minas Gerais): belo-horizontino.
Boa Vista (Roraima): boa-vistense.
Brasília (Distrito Federal): brasiliense.
Campo Grande (Mato Grosso do Sul): campo-grandense.
Cuiabá (Mato Grosso): cuiabano – de forma jocosa, os cuiabanos são muitas vezes referidos como “papa-peixes”.
Curitiba (Paraná): curitibano.
Florianópolis (Santa Catarina): florianopolitano.
Fortaleza (Ceará): fortalezense.
Goiânia (Goiás): goianiense (o natural do estado é um goiano).
João Pessoa (Paraíba): pessoense.
Macapá (Amapá): macapaense.
Maceió (Alagoas): maceioense.
Manaus (Amazonas): manauense.
Natal (Rio Grande do Norte): natalense – de forma jocosa, os natalenses são referidos como “papa-jerimuns”.
Palmas (Tocantins): palmense.
Porto Alegre (Rio Grande do Sul): porto-alegrense.
Porto Velho (Rondônia): porto-velhense.
Recife (Pernambuco): recifense.
Rio Branco (capital do Acre): rio-branquense.
Rio de Janeiro (Rio de Janeiro): carioca – não confundir com fluminense, natural do estado do Rio de Janeiro.
Salvador (Bahia): soteropolitano ou salvadorense – muitos portugueses costumam chamar a cidade de São Salvador, mas o nome é apenas Salvador.
São Luís (Maranhão): são-luisense ou ludovicense (forma pouco usada).
São Paulo (São Paulo): paulistano – não confundir com paulista, que é o natural do estado de São Paulo.
Teresina (Piauí): teresinense.
Vitória (Espírito Santo): vitoriense ou capixaba.