"I eat lunch at a restaurant."
It's like the location particle (not sure on the exact name). It just shows that the action takes place at the noun before the で.
で indicates where the particle is performed, whereas に indicates the direction /towards/ an action is performed. So に is mostly used with verbs which indicate notion, such as 行く(to go). There are some exceptions such as すむ(住む) which takes に. Also ある and いる take に.
で is where an action will take place, like "at". に is indirect object or location of direction like "to". へ is like に but more general like "towards".
Apparently not, since omitting it doesn't count it as wrong. I guess it will just sound less respectful of you don't put it.
It seems something changed since then, because it marked my answer as wrong for omitting it.
I omitted it as well and was not marked wrong. Either they changed it again, or there was something else that was wrong/different with your sentence.
Man, this one is so hard for me to figure out, ive been stuck on it for ages.
Can someone more fluent in Japanese please break it down for me?
Don't know about fluent, but...
レストラン: Restaurant で: Particle to indicate that the action is happening at the just-stated location (the restaurant) お: Honorific (because you need to be polite to your lunch, apparently) ひるごはん: Literally 'day rice', the Japanese term for lunch を: Particle to indicate... Something. I think it's the passive sense, but I haven't really internalized that part yet. In this sentence, it indicates that the action is being applied to the part of the sentence that was just said. 食べ: To eat ます: Auxiliary verb, here used to conjugate the other verb into an actual action, or something. At any rate, when it you add ます or です to the end, you're sayng that things are happening (as opposed to asking about it (ですか) or saying it is not the case (ません))
This is basically correct, except for the following details:
The function of を is to mark the grammatical (direct) object, which as you say is the thing (this may include people) that is being acted upon or directly affected by the action.
ます is not an auxiliary verb, it is an ending (like English -s or -ed) which says that the verb is in non-past tense (present or future), positive (that is, not negated) and in the polite form. (We know that it isn't an auxiliary because it cannot stand on its own, like です can.)
The question particle か can be used with any form of any verb and should not be conflated with です: 食べますか "Do you eat?", 食べませんか "Do you not eat?", 食べましたか "Did you eat?", 食べませんでしたか "Did you not eat?", and so on.
It's showing that "ひるごはんを レストランで食べます" is also correct. Is there a difference in connotation with the different order?
Yes. Putting the object (ひるごはんを) just before the verb is the "neutral" word order, so if you put anything else between them that part becomes emphasized: "I eat lunch at a restaurant" (as opposed to, say, at home, in a cafeteria or from a bento). You can read more about this at https://8020japanese.com/japanese-word-order/