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.
Mare
and 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