Out of your shortlist, I would recommend Lisbon. It's not as big but punches above its weight in most of your other criteria.

The Brazilian cities you described do not have good public transport or bikes, and almost no foreigners. The advantage is that cost of living is very low, but Lisbon is also not that expensive as well.