Learn Russian: Мы начинаем этот проект с новыми партнёрами. - We are starting this project with new partners.

The preposition с (meaning "with") requires the instrumental case. Since we are talking about plural partners, we use the instrumental plural endings: -ыми for the adjective (новыми) and -ами for the noun (партнёрами).

Why didn't этот проект change its ending if it's the direct object?

As the direct object of начинаем (we are starting), it is in the accusative case. Because masculine nouns that are inanimate (objects, not living beings) do not change their endings in the accusative, этот проект looks exactly the same as its basic dictionary form.

Does the preposition с always trigger the instrumental case?

It does when it means "with" (doing something together with someone or something), like с новыми партнёрами here. But watch out: when с means "from" or "off of" a place, it takes the genitive case instead.

What is the dictionary form of начинаем?

The infinitive is начинать (to begin or start). It follows the standard first conjugation pattern, so for мы (we), you drop the -ть and add the ending -ем.