"He lives in a different city."
Translation:Han bor i en annan stad.
You'd use olika to differentiate between multiple things, since it's in plural. For instance: "de bor i olika städer" ("they live in different cities").
When using it in singular, its meaning is restricted to a comparison of behaviour or appearance. So "han är olik de andra" means "he is unlike the others."
Hence, "han bor i en olik stad" would mean roughly "he lives in a city that does not appear to be like", and has about the same grammatical weirdness to it.
Andra works with plurals and/or definites. This sentence is neither, so you have to go with annan.
Ah, so then:
"Han bor i en annan stad." "De bor i andra stader." (and not annan) "Den andra stad." (and not annan)
"annan" to me, means "other" -- even in this context. I used "annorlunda" instead. Why won't this work?