Eu gosto de lentilhas com arroz.

Because gostar normally uses the preposition de before the thing you like.

So the pattern is:

• gostar de + noun
• gostar de + infinitive

Examples:

• Gosto de lentilhas.
• Gosto de arroz.
• Gosto de cozinhar.

For an English speaker, it helps to learn it as one unit: gostar de = to like.

Not usually.

In Portuguese, the verb ending often already shows who the subject is. Gosto means I like, so Eu can be omitted:

• Eu gosto de lentilhas com arroz.
• Gosto de lentilhas com arroz.

Both are correct.

You would include Eu if you want emphasis, contrast, or clarity:

• Eu gosto de lentilhas, mas ele não.

In European Portuguese, leaving out the subject pronoun is very common.

Gosto is the 1st person singular present tense of gostar.

So:

• eu gosto = I like

A few other forms:

• tu gostas = you like
• ele/ela gosta = he/she likes
• nós gostamos = we like
• vocês gostam = you like
• eles/elas gostam = they like

In this sentence, the present tense expresses a general preference: I like lentils with rice.

Because Portuguese often leaves out the article when talking about food in a general sense.

So:

• Gosto de lentilhas.
• Gosto de arroz.

This sounds natural when you mean the food in general, not a specific portion or a specific dish you already know.

If you mean something specific, you may use an article:

• Gosto das lentilhas que a tua mãe faz.
  = I like the lentils your mother makes.
• Gosto do arroz deste restaurante.
  = I like the rice in this restaurant.

So in your sentence, the lack of articles makes it sound general: you like lentils with rice as a kind of food.

This is similar to English.

• lentilhas is usually treated like lentils — plural
• arroz is usually treated like rice — singular/mass noun

So:

• lentilhas = lentils
• arroz = rice

Even though both refer to food, Portuguese does not have to treat them the same way grammatically.

It most naturally describes lentilhas.

So the structure is basically:

• Eu
• gosto de
• lentilhas com arroz

That means I like lentils with rice.

In other words, de introduces the whole thing you like, and that whole thing is lentilhas com arroz.

Because arroz is not a second separate object of gosto here.

The sentence does not mean:

• I like lentils, and I like rice

It means:

• I like lentils with rice

So de only appears once, before the whole phrase:

• gosto de lentilhas com arroz

If you wanted to say you like both foods separately, you could say:

• Gosto de lentilhas e de arroz.

Usually it just means with rice, and the exact relationship depends on context.

It could mean:

• lentils served alongside rice
• lentils combined with rice
• a dish that includes both

If you need to be more specific, Portuguese can say that more clearly:

• lentilhas servidas com arroz = lentils served with rice
• lentilhas misturadas com arroz = lentils mixed with rice

But your original sentence is perfectly natural as a general statement.

Yes, but the focus changes slightly.

• Gosto de lentilhas com arroz puts lentilhas first
• Gosto de arroz com lentilhas puts arroz first

Both can be correct, but they may suggest a slightly different emphasis depending on what you consider the main item in the dish.

A helpful approximation is:

eh-o GO-sh-tu d(uh) len-TEE-lyash kõ ah-HOZH

A few important pronunciation points:

• gosto: the s sounds like sh because it comes before t
• de is often reduced in European Portuguese, sounding like a very short d(uh) or dih
• lh in lentilhas is like the lli sound in million
• final -s in lentilhas sounds like sh
• the rr in arroz is a strong guttural r in European Portuguese
• final z in arroz sounds like sh at the end of the sentence

A rough IPA version is:

[ew ˈɡɔʃtu dɨ lẽˈtiʎɐʃ kõ ɐˈʁoʃ]

Yes, it is completely natural in European Portuguese.

A Portuguese speaker in Portugal would understand it immediately, and it sounds like a normal everyday sentence expressing a food preference.

You could also hear the subject omitted very often:

• Gosto de lentilhas com arroz.

That is probably even more common in ordinary conversation.