Really? I thought good old imperative programming was the best starting point. Concepts like assignment, branching, looping. IMHO goto is actually useful at that point and structured programming is an abstraction that takes a little while to wrap your head around. Perhaps it's due to the way I learned that I think some things are more basic (no pun intended). Either way I don't think high level abstract concepts like functional programming are even relevant in the real world of software development - abstract stuff is CS, basic stuff is for everyone else who has to take a programming course.

    x = 1
    x = 2

If we stick to immutable values and recursion, and functions that are, well, functions, we get something that corresponds quite closely to first-year mathematics, which makes it easy to learn at the same time.

Using a modern imperative language doesn't prevent you from adding complexity a bit at a time, and -- especially initially -- getting the advantages of teaching things in a functional style.

[1] but not object fields, as objects are taught as containers of mutable state, usually late in the course.

Exactly! Intro courses are usually - with good reason - taught in functional style. Which suggests that a language where that style is more natural and appropriate might be a better fit for those courses than Python.

(Though OTOH I wouldn't advocate a language where IO is anything more complex than a function call)

This is nothing but FUD and you should be ashamed of yourself.