Learn Hardcore Icelandic: Ég spyr þjóninn hvort ég megi fá annan matseðil. - I ask the waiter whether I may get another menu.

It’s definite: the waiter → add the suffixed article -inn.
It’s in the accusative singular, because it’s the direct object of spyr (whom do I ask? the waiter).

Declension (singular, indefinite vs. definite):

Nominative: (þessi) þjónn – þjónninn
Accusative: (ég sé) þjón – þjóninn
Dative: (ég tala við) þjóni – þjóninum
Genitive: (húss) þjóns – þjónsins

So in Ég spyr þjóninn …, þjóninn is accusative definite: the waiter as the person being asked.

Why is the waiter in the accusative and not in the dative?

The verb að spyrja governs its object in the accusative:

að spyrja einhvern – to ask someone (accusative)

Some verbs in Icelandic take dative objects, but spyrja is not one of them. Compare:

Ég spyr þjóninn. – I ask the waiter. (accusative)
Ég hjálpa þjóninum. – I help the waiter. (dative, because hjálpa takes dative)

So the case is determined by the verb’s valency, not by a general rule like “person = dative”.

What exactly does hvort mean here, and how is it different from ef?

In this sentence, hvort means “whether / if (in the sense of whether or not)” and introduces an indirect yes/no question:

… hvort ég megi fá annan matseðil.
→ … whether I may have another menu.

The contrast:

hvort = whether / if (in reported questions, yes/no alternatives)
ef = if (in conditional clauses, “on condition that”)

Examples:

Ég veit ekki hvort hann kemur.
I don’t know whether he is coming.
Ef hann kemur, þá förum við.
If he comes, then we’ll go.

Using ef in this sentence would sound wrong, because you’re not giving a condition; you’re reporting a question about permission.

Why is the word order hvort ég megi fá and not hvort megi ég fá?

Because hvort here introduces an indirect question, which in Icelandic usually has statement word order (subject–verb–object), not the question word order used in direct questions.

Direct question:
Megi ég fá annan matseðil? – May I have another menu?
(verb first)
Indirect question (reported):
Ég spyr hvort ég megi fá annan matseðil.
(subject ég before the verb megi)

So in subordinate clauses like this, Icelandic normally follows the same S–V order as a statement:

Statement: Ég megi fá… (as part of a larger structure)
Indirect question: hvort ég megi fá…

Hvort megi ég fá… inside this kind of clause is unusual and feels like embedding a direct question; hvort ég megi fá is the standard and most natural order.

What form is megi, and how is it different from má?

Both megi and má come from the verb að mega (may, be allowed to), but they are different moods:

Má = present indicative, 1st/3rd person singular
- Ég má fara. – I am allowed to go.
Megi = present subjunctive, 1st/3rd person singular
- Megi ég fara? – May I go? (more tentative / polite / hypothetical)

In your sentence:

hvort ég megi fá annan matseðil
literally: whether I may (be allowed to) get another menu

The subjunctive is common:

in polite requests: Megi ég fá vatn?
in reported or uncertain situations, like something being asked about or wished for.

You could hear hvort ég má fá annan matseðil, which is also grammatically fine, but megi sounds a bit more formal/polite and fits the “asking permission” context very well.

Why are there two verbs together: megi fá?

This is a modal verb construction, very similar to English:

megi – may / be allowed to (modal verb)
fá – to get / receive (main verb, infinitive)

So:

megi fá ≈ may get / may have

In Icelandic, modal verbs like geta (can), eiga (should, ought to), mega (may), etc., are followed by an infinitive:

Ég get talað. – I can speak.
Ég á að læra. – I’m supposed to study.
Ég má fara. / Ég megi fara. – I may go.

In your sentence, megi is the finite (conjugated) verb; fá stays in the infinitive.

What does annan mean exactly, and what form is it?

Annan is the accusative masculine singular form of the adjective/pronoun annar.

Annar has two main meanings:

Another / a different one
- Get ég fengið annan matseðil?
  Can I get another menu (an additional/different one)?
Second (as an ordinal number)
- annar dagur – the second day

Here it clearly means “another (one), an additional one”, not “second in order”.

Declension (singular, key forms):

Masculine: nom annar, acc annan
Feminine: nom önnur, acc aðra
Neuter: nom/acc annað

Because matseðil is masculine, accusative singular, the adjective must agree, so you get annan matseðil.

Why is it matseðil and not matseðill?

The base word is matseðill (menu, masculine). In the sentence, it’s in the accusative singular as the direct object of fá (to get), and this noun changes its ending in the accusative.

Singular declension:

Nominative: matseðill – a menu (subject)
Accusative: matseðil – a menu (object)
Dative: matseðli
Genitive: matseðils

So:

Matseðill er á borðinu. – A menu is on the table. (nominative)
Ég vil fá matseðil. – I want to get a menu. (accusative)

In your sentence, fá takes its object in the accusative, so matseðill becomes matseðil.

Could you also say annan matseðilinn, or would that change the meaning?

Yes, it would change the meaning.

annan matseðil – another menu / one more menu (indefinite)
annan matseðilinn – the other menu / the second menu (definite, a specific “other” one)

The suffixed article -inn makes it definite:

matseðilinn = the menu
annan matseðilinn = the other (specific) menu

When you’re just asking a waiter for an additional copy of the menu, you normally want the indefinite phrase annan matseðil, not a specific named “other” menu.

Do I really need to repeat ég in hvort ég megi, or can I leave it out?

Yes, you should keep ég. In normal Icelandic, subject pronouns are not dropped the way they can be in some other languages.

Correct/natural:
Ég spyr þjóninn hvort ég megi fá annan matseðil.
Without the second ég:
Ég spyr þjóninn hvort megi fá annan matseðil.
This is either ungrammatical as-is or sounds like a rather impersonal, generic construction (“whether one may get another menu”), which is not how you’d usually phrase a personal request here.

So: repeat ég as the subject of megi; each finite verb in its own clause needs a subject.

Is this a natural way to ask for another menu in Icelandic, or is there a more common phrasing?

Your sentence is grammatical and natural as a narrative:

I ask the waiter if I may have another menu.

That’s exactly how you’d report the action in a story or conversation.

However, what you’d actually say to the waiter is usually shorter and direct, for example:

Má ég fá annan matseðil?
May I have another menu? (very common, polite enough)
Get ég fengið annan matseðil?
Can I get another menu? (also common)
Gæt(i) ég fengið annan matseðil?
Could I get another menu? (extra polite / soft)

So:

To describe what you’re doing to someone else:
Ég spyr þjóninn hvort ég megi fá annan matseðil.
To actually ask the waiter:
Má ég fá annan matseðil? or Get ég fengið annan matseðil?

How should I roughly pronounce Ég spyr þjóninn hvort ég megi fá annan matseðil?

A rough, English-friendly approximation (stressed syllables in CAPS):

Ég – like “YAY” but shorter (YEH / YAY)
spyr – “spir” (like sp*r + *ear but short: SPIR)
þjóninn – THYOH-nin
- þ like th in thing
- stress on þjón
hvort – roughly KVORT (the hv is pronounced like kv for most learners)
megi – MEY-yi (first syllable like may, second like yi in yip)
fá – like FAU (“fow” in cow)
annan – A-nan, stress on first A
matseðil – MAHT-se-thil
- ð like the th in this
- stress on MAT

All main stress is on the first syllable of each word, which is a strong, regular pattern in Icelandic.