Learn Hardcore Spanish (Latin America): Probamos paella por primera vez y la encontramos deliciosa. - We tried paella for the first time and found it delicious.

Probamos is indeed identical for nosotros in the present (“we try”) and in the preterite (“we tried”). In this sentence, por primera vez (“for the first time”) tells us it’s a completed action in the past, so probamos is the preterite. If you wanted to express an ongoing or habitual tasting in the present, you could say estamos probando paella (“we are trying paella”) or probamos paella a menudo (“we try paella often”).

Why is there no article before paella? Couldn’t I say la paella?

When you talk about a dish in a general or unspecified sense—“paella” as a type of food—Spanish normally omits the article. Saying Probamos paella is like “We tried paella (some).” If you refer to a specific paella (the one at that restaurant, for example), you could say Probamos la paella.

What does por primera vez mean, and why is it por and not para?

Por primera vez literally means “for the first time.” In Spanish, por is used in idioms expressing cause, duration, motive, or in this case a point in a sequence (“for the first time,” “for the second time,” etc.). Para expresses purpose or destination, so it wouldn’t work here.

Why is la placed before encontramos? Could you say encontramos la deliciosa?

In Spanish, direct object pronouns like la must appear immediately before a conjugated verb. La stands for la paella (feminine sing.). So you say la encontramos (“we found it”). The adjective deliciosa follows the verb, not the pronoun. Encontramos la deliciosa would be ungrammatical.

Why is the adjective deliciosa feminine? What if I wanted to talk about multiple dishes?

Adjectives in Spanish agree in gender and number with the noun they modify. Paella is singular feminine, so you use deliciosa. If you tried two different vegetarian paellas, you might say Probamos paellas vegetarianas por primera vez y las encontramos deliciosas (plural, feminine).

Why use encontramos deliciosa instead of saying nos gustó la paella?

Both express a positive opinion, but the constructions differ:
• Encontrar + direct object + adjective (encontramos la paella deliciosa = we found the paella delicious).
• Gustar + indirect object pronoun (nos gustó la paella = paella pleased us).
You can choose either; encontrar emphasizes your personal judgment, gustar is more idiomatic for likes.

Why isn’t the subject pronoun nosotros included? Would it ever be necessary?

Spanish verbs are inflected for person and number, so the subject pronoun nosotros (“we”) is redundant and usually dropped. You’d only include nosotros for emphasis or contrast:
“NOSOTROS probamos paella…,” maybe if you’re distinguishing your group from someone else. Otherwise it’s omitted.