If you ask me, I do think "Arabian" is more proper than "Arab" here. English is not my first language, but it feels so. I mean, we have "Arabian Nights" so the adjective "Arabian" is not used for persons only but for objects as well. I guess it is one of these Duolingo moments that are completely illogical (and they are many).
While the word 'Arabian' will be understood by most native English speakers when used in the way you suggest, it also sounds old-fashioned and a little odd when applied to cities or people (outside of 'Arabian Nights', it's only used otherwise when talking about horses).
You might find this explainer helpful on when to use Arab/Arabic/Arabian: https://brians.wsu.edu/2016/05/17/arab-arabic-arabian/ (N.B. the pronunciation note is for US English - in my variety [British] we say 'Arab' with a short 'a' as in 'bat'.)
The name (Medina), which is a city in Saudi Arabia, is indeed المدينة and it is a common and abbreviated form for المدينة المنورة (al-madínatul-munawwarah); meaning the enlightened city. The old name for this city or town before the immigration of prophet Mohammed (PBUH) to it was Yaþrib يثرب.
On a side note, the Maltese town of Mdina is also of the same origin, مدينة meaning city.
As a general rule, a sentence in Arabic does not start with an indefinite noun. Except in few special conditions.
Here, we have a phrase and not a full sentence. Just a noun (city) with its adjectives that describe it; (big) and (Arab). Typically in Arabic the order of the adjectives would be the reverse of that in English. Or put in another way, the most relevant follows the noun directly, and then followed by adjectives less relevant. Sometimes "and" (و) can be used between adjectives as well.