cat is arguably from catenate, which is the smarter, shorter version of concatenate. By default, unadorned catenation is a joining (literally "making into a chain"), which is always together/with, so the con prefix is redundant. If you ever need a derivative of catenate that means splitting apart, you can coin discatenate, where the dis then plays an essential role.
Also, why is it that people are gregarious when they congregate, and not congregarious? Or why didn't they just gregate? There was such a Latin cognate verb without the con attached.
Because that's not how the prepositions worked in Latin. E.g. "Marcus ex casa exit" ("Marcus went out of the house") requires both the "ex" preposition and the "ex-" prefix in the verb. Heck, even today similar things can happen in English: "they gathered together", that sentence has two instances of "gather" in it.
Also, why is it that people are gregarious when they congregate, and not congregarious? Or why didn't they just gregate? There was such a Latin cognate verb without the con attached.