Why do many languages have both grammatical genders and declensions?

Your insight is correct, Riccardo: declensions and genders are both classes of nominals. The difference in Indo-European is that gender, not declension, is what governs the agreement of non-nouns with nouns, while declension is how the morphology of nouns themselves works.

So in Ancient Greek, gender only affects the ending of the noun in patches—a couple of cases differ by gender in each declension. But a third declension noun will agree in gender with a 1st/2nd declension adjective or pronoun, without any problem.

You wouldn’t design things like that; it’s kind of a happenstance. Gender is slightly (only slightly) more predictable than an arbitrary declension, which makes it a better candidate for agreement. But it’s an accident of how Indo-European developed. And recall that the feminine is a late development in Indo-European anyway, originating in a collective suffix.

Many languages outside Indo-European have noun classes, and the term “noun classes” is used precisely because in those languages, there is not much of a distinction between declension and gender to be made. Swahili has 18 noun classes; that number sounds more like a declension count than a gender count, but there is a strong semantic component to them (as there is in noun classes in general), and animacy takes over as a factor in agreement anyway.