Oh, yeah, the nouns are gendered - everything is gendered! And it must be memorized, there is no rule. Same is true for all Romance languages (Portuguese, Spanish, French, etc.) AFAIK.

Btw. it is "das Frühstück" as well.

But you get laughed at when saying "das Cola" in Germany, but yelled at being a stupid German when saying "die Cola" in Vienna. Which makes the whole thing great, because it obviously annoys us a lot, both is correct though, and it totally doesn't make a difference what the gender of the thing is :)

We have lot's of words where the "Duden", the official dictionary has an "Austrian also: ..." alternative gender. And then there are colloquial habits that are utterly out of spec which make me furious to be honest. Who the hell thinks "das Teller" sounds right?!