According to https://hu.wiktionary.org/wiki/f%C5%91n%C3%B6k it is indeed based on "fő", but -nök is not a standalone word, it is a noun generator (https://wikiszotar.hu/ertelmezo-szotar/Nok brings some examples such as ügynök / agent, ülnök / sitter). Not sure how to help with the memorizing it though, maybe the german Haupt - Hauptling helps?
As for "főúr", that is not head waiter, rather a lord of a land. Google says it translates to "thane".
Köszönöm szépen, that helps. I once was told that one can use főúr to call (or maybe address) a server in a restaurant, and I assumed that it was a Mitteleuropa expression (German: Herr Ober, Czech: pane vrchní, Slovak: pán hlavný – all without the word server or waiter).
If I should ever visit Hungary again I will be more careful about this expression. (At the moment It does not look like I will.)