Quando está frio, eu começo a espirrar.

Yes, Quando faz frio is very common and close in meaning: When it’s cold / When it gets cold.
A rough nuance:

• Está frio often feels like a specific, immediate condition (right now).
• Faz frio is a very standard “weather expression” and can feel slightly more general.
  In everyday speech, both are widely used and usually interchangeable in sentences like this.

The present tense here expresses a habitual/general truth: whenever it’s cold (in general), that’s what happens. English also uses present for this: When it’s cold, I start sneezing.

If you’re talking about a specific future time, Portuguese often uses the future subjunctive:

• Quando estiver frio, eu vou começar a espirrar. = When it’s cold (later), I’m going to start sneezing.

When a dependent clause comes first (here, the Quando... clause), Portuguese commonly uses a comma to separate it from the main clause:

• Quando está frio, eu começo a espirrar.

If the order is reversed, the comma is often omitted:

• Eu começo a espirrar quando está frio.

You can drop it most of the time because the verb form already indicates the subject:

• Quando está frio, começo a espirrar. = natural and correct.

Keeping eu can add emphasis or clarity (especially in contrast): Eu começo... (but someone else doesn’t).

In Portuguese, começar + a + infinitive is the most common pattern for “to start doing something”:

• começar a espirrar = to start sneezing

That a is a preposition required by começar in this construction; it doesn’t translate neatly into a separate English word.

You can, but it changes the feel:

• Começo a espirrar = I start to sneeze (focus on the beginning of the action)
• Começo espirrando = more like I start off by sneezing / I begin (the situation) sneezing (it can sound like sneezing is the first thing that happens in a sequence)

For your sentence, começo a espirrar is the most straightforward.

The verb is começar (infinitive). In Portuguese spelling:

• ç is used before a, o, u to keep the “s” sound: começar
• Before e, i, a plain c already has the “s” sound, so it becomes começo (no cedilla needed)

So: começar → eu começo, você começa, eles começam.

A practical Brazilian-style guide:

• Quando ≈ KWAN-doo (the qu is like kw)
• está ≈ es-TAH (stress on the last syllable)
• frio ≈ FREE-oo (two vowel sounds)
• começo ≈ ko-MEH-soo (stress in the middle)
• espirrar ≈ es-pee-HAH (in many BR accents, rr sounds like an h)

Also, in fluent speech está can reduce to tá: Quando tá frio, eu começo a espirrar.

Yes, they often point to slightly different ideas:

• Quando está frio = When it’s cold (state)
• Quando fica frio = When it gets cold / becomes cold (change into that state)

Both can work, but fica frio highlights the transition (the moment it turns cold).