In my opinion, the most likely translation of the sentece is:
Our sea has many docks
Mare Nostrum was a common name given by the Romans to the Mediterranean Sea around the I century AD, since the empire possesed all of its coast by that time.
Regarding your question in the title, yes adjectives and pronouns must agree in gender, number and case with the respective noun. In this case,
nostrum acts as an adjective, since it isn't replacing any nouns.
nostrum are neuters in nominative, singular (sing. neut. are the same in nom., voc., and acc.).
Portus belongs to the fourth declension, meaning that it forms its accusative plural with -us, just as its nom. singular. In this case,
portus agrees with
plurimos to say many docks as the object of the verb
habere (hence it is not in genitive).
Edit: about the alternative sentence you offered: Since
portus is plural,
mare plurimos nostrorum portus habet agrees in number: no need for partitive plural. However, as @brianpck notes, portus should change to
portuum in order to be in genitive and agree with
nostrorum, so that the sentence can mean The sea has most of our harbours.
Hope it helps