Classical Arabic does have Verb-Subject word order. But in this sentence, and sentences that show possession in general, the construction is "At [possessor] [possession]", rather than "[possessor] has [possession] like in English. So, instead of a verb, a preposition - the word عِنْد - is expressing the meaning of "have", and that indeed does come first before possessor.
Shouldn't "كراج / garage" have a different ending than the nunation present in the audio? Isn't "كراج / garage" an accusative object and should therefore end differently?
Merte18 - that's typically the case, but عِنْد is actually a preposition rather than a verb. Instead of a verb meaning "have" like in English or Spanish, Arabic uses a construction that means something like "At [possessor] [possession]. So instead of "Shadi has a big garage" the literal translation is "At Shadi big garage (or garage big)". In that case, the noun "garage" should have the -un nunation, being in the nominative case. However, the object of عِنْد should technically be in the dative/genitive, since this is the case that nouns take after a preposition. The vowel for this case is -i, or with nunation, -in.