At least with country and city names things are not that complicated. There are a few rules that apply to most countries and cities: most city names are feminine, but are used without article (Tóquio é gigantesca); country names are masculine except if they end with an a, in which case they are nearly all feminine, and most of them are used with article. I’ll deal with the exceptions below.
Before we go one, the question is just whether the name takes a definite article. If it does, say o Brasil, then it logically is estou no Brasil, venho do Brasil, vou ao Brasil, viajei pelo Brasil; if it doesn’t, say Portugal, then it is estou em Portugal, venho de Portugal, vou a Portugal, viajei por Portugal.
One rule that applies across the board—to countries, cities, and islands—is no article for places named after saints, such as São Paulo or Santa Maria.
Countries
In fact the names of most countries follow the gender pattern of common names. It is masculine if the name ends with an o (o México, o Japão) and feminine if it ends with an a (a China, a Índia). The notable exceptions are o Uganda, o Ruanda, o Quénia, o Botswana and o Gana. Other masculine names ending in a—o Panamá, o Canadá—are not quite exceptions, as they follow the pattern of common names such as o alvará, o pancá, o rajá. Names ending in e tend to be complicated (a sede, o lote), but for some or no reason nearly all, if not all, names of countries ending in e are masculine (such as o Chile, o Vietname, o Iraque). Now we have just a couple of countries left, and nearly all have masculine names (ending in i, u, r, s and l).
Most country names are used with the definite article. The exceptions I can remember are:
(a) Angola, (o) Cabo Verde, (a) Cuba, (o) Israel, (o) Marrocos, (o) Madagáscar, (o) Moçambique, (o) Omã, (o) Portugal, (o) São Tomé e Príncipe, (o) Timor Leste
Even though these names are used without article they have a gender nonetheless. So, Portugal é lindo, but Angola é linda. And you can actually use the article in some constructions: a Angola da minha infância.
Then there are couple of European countries for which the definite article is optional, and more often than not omitted, in European Portuguese but compulsory in Brazilian Portuguese:
Espanha, França, Inglaterra, Itália
And Portuguese speakers appear divided between Taiwan and o Taiwan.
Towns and Cities
The rule is no article. The exceptions are towns and cities that took their names from common names. Examples.
o Porto (‘the port’), a Guarda (‘the guard’), o Rio de Janeiro (‘the river of january’), o Recife (the article is sometimes omitted, ‘the reef’), a Figueira da Foz (‘the fig tree of the (river) mouth’)
An exception to the exception: o Cairo to my knowledge does not come from any common name.
States and Regions
Most Brazilian States take a definite article. The exceptions are:
Alagoas, Goiás, Mato Grosso, Mato Grosso do Sul, Minas Gerais, Pernambuco, Rondónia, Roraima, Santa Catarina, São Paulo
In Portugal nearly all regions take a definite article: o Algarve, o Alentejo, o Minho, etc. Trás-os-Montes is the only exception that comes to my mind.
I’m now mentally surveying US states, and I would use a definite article, almost always the masculine, with nearly all of them: a Califórnia, a Flórida, o Alabama, o Kansas, o Arizona. But em New Hampshire. But that’s just because it sounds good to me. Not absolutely sure about other people.
Smaller Places
Here I am at loss myself too. Thinking of neighbourhoods of Lisbon, there seems to be a tendency for names derived from common names to have the article (a Lapa, o Lumiar, os Olivais, o Bairro Alto) and no article otherwise (Alvalade, Benfica, Alfama). But I can find exceptions such as Campo de Ourique and Sete Rios (no articles).
