For example, would an ancient Latin speaker tell me that their nouns were masculine or feminine? Or more to the point, when did we start discussing this fairly common linguistic feature in gendered terms?
A lot of this is more of a linguistics topic, but I can talk about the specific historical question.
Yes, that is exactly what a Roman grammarian of let's say the fourth century CE would tell you: nouns have gender and that gender is masculine, feminine, neuter, or possibly can change based on the referent.
Latin is a highly inflected language in which the endings of nouns change based on number (singular or plural) and case (grammatical role). In addition, adjectives must agree with nouns in number and case as well as one other feature. As the Romans put it, nouns have a genus (which means "category" but which we translate in this context as "gender"), which is either masculinum, femininum, or neuter (which we translate respectively as "masculine," "feminine," and "neuter"). Nouns inherently have a gender but adjectives do not, so you have to know the noun's gender to make the adjective agree. The gender is often but not always apparent from the noun's endings and how they inflect.
The grammarian would probably go on to explain that masculine nouns refer to male human beings or things that are somehow male; female nouns refer to female human beings or things that are somehow female; and the relatively rarer neuter nouns refer to things that seem to lie outside these categories. Roman grammarians were very interested in nouns whose form seemed to place them in one gender but, in their view based on ancient sources, current usage, and application of reason, seemed to belong to a different gender. E.g., agricola looks and inflects like a feminine noun, but it was considered masculine because that's how it had been treated by literate speakers and writers and it meant "farmer," a male occupation. Nauta ("sailor") and pirata ("pirate") were likewise feminine in form but considered masculine. Conversely nearly all trees were considered feminine even though some like quercus ("oak") really looked masculine.
In a few cases, the grammarians conceded that you could make adjective fit the actual referent of the noun: so-called "common" gender. This was especially seen with animals where there was one noun referring to both male and female individuals; also some professions such as sacerdos ("priest") that might be held by male or female humans.
That's the source of our grammatical terminology. In fact, the English word "gender" is derived from Latin genus and had the primary meaning of this type of grammatical category. Using "gender" to refer to actual things rather than words is really seen only starting in the 20th century, in part as a way to avoid the word "sex." Use of, umm, gendered terminology like masculine, feminine, and neuter to describe grammatical genders is likewise derived from the Roman grammarians' practices. Linguists could, perhaps, have used terminology like "noun classes" and numbered the classes (as is done for Bantu) but this is not the way the field developed because the Romans' own model for using Latin was very influential and worked pretty well for describing many other languages that have something like gender (basically, other words agreeing with some feature of nouns). In part that is because many languages follow (or historically followed) patterns similar to Latin: the nouns referring to male and female humans often followed different inflection patterns.
Notes for students of languages: