As a native speaker of a language with grammatical gender (Croatian; I've also learned Russian and a bit of German)...

What exactly does gender achieve in a language?

In Slavic languages it serves as an additional syntactic "connector" between words. Masculine nouns are accompanied by masculine forms of adjectives, feminine by feminine, etc. (Other than adjectives, this also applies to pronouns, some numbers and verbs.) This isn't necessary for successful communication, but it can somewhat reduce ambiguity and, along with other trickier parts of grammar such as cases, allows for quite a bit of freedom in how a sentence can be organised. English can be limited in that regard, with its stricter rules on word order, although its lack of grammatical gender is not the most significant factor.

Is it literally thinking about nouns as male or female, or is it just a weird name for the concept?

It's more of a name, true. There are prototypical words and situations where grammatical gender really is the same as biological sex (e.g. when referring to specific real people - just as you'd call a woman 'she' in English, so do you have to use feminine adjectives when referring to her), and that relationship is, for the sake of simplicity, projected onto the entirety of nouns in the language.

Who decides gender when a new noun is made?

In Slavic languages, it's really simple because the noun endings usually correspond to gender. There are exceptions and, so to say, "subsystems" within the general system, and there can be changes in how that system works, but the point is that it's based on a set of rules that speakers do know intuitively.

German doesn't have such a clear system of genders that is visible within each word (the endings usually don't tell you anything useful; if the noun ends on 'e' it's relatively likely it's feminine, but that's about it, as far as I know). Yet, interestingly enough, there was an experiment where native Germans were provided with made-up words, and were asked to determine their gender. The majority of people agreed on their choices. So, clearly German does have some rules and procedures to determine gender, even if they're opaque.

What about borrowed words from other languages?

Same as above. I can provide some illustrative examples if you want?

Do you sound stupid if you speak French without using it

I tried to imagine some sentences of that sort in Croatian, with incorrect genders, and it doesn't sound outright stupid, just odd. Some situations allow for some leeway in choice of gender too, and natives can make mistakes if they don't think too clearly which word they intend to use, and none of that is especially bothersome to a native's ear.