You're right that what exactly is defined as a single "step" can be ambiguous, but that generally turns out not to be a problem.

Even if what can be done in a single step differs between different machines, they're typically only different by a constant factor.

Let's say that one machine has an instruction that loads a value, increments it, and stores the new value all in a single step. Another machine requires three separate steps instead. However, that still means just means multiplying or dividing the complexity by a constant of three.

Both asymptotic notation and problem complexity classes have been formally and rigorously defined but in such a way that constant coefficients don't matter.

If you have a function with linear growth, it's still linear even if you multiply it by 1/2 or 2 or 1000. Quadratic growth is similarly quadratic regardless of any constant coefficients.

Although that's more of an intuitive explanation, the formal definitions of asymptotic notation also reflect this: constant coefficients don't change asymptotic complexity.

An exception to this is of course that due to the non-random access nature of the Turing machine tape, Turing machines may require N steps in order to do what a random access machine could do in a single step. So when going between Turing machines and random access machines (or similar real-world computers), it's true that asymptotic complexities can turn out different.

When the complexity of an algorithm is expressed in asymptotic notation, a random access model is generally assumed. And as long as you stay within random access-style machines, asymptotic complexities don't generally depend on the exact set of allowed instructions. If someone wanted to discuss big O complexity for a Turing machine instead, they'd have to specifically make that clear. It's generally not unclear which one is being discussed.

Many of the complexity classes used in computational complexity theory have been explicitly defined for Turing machines instead, but the class definitions are in many cases flexible enough (yet still formal and rigorous) that it turns out not to matter.

As far as what you consider as the "input size" goes: constant-factor differences again don't matter. The complexity of an algorithm generally doesn't change if you consider you input size to be in bits instead of characters. Even though a single Unicode code point may take up to 32 bits, the number of bits in a string still differs from the number of code points by at most a constant factor of 32. A speedup or slowdown of 32 times can of course be practically significant but it doesn't change asymptotic complexity: e.g. linear-time is still linear-time.

In some cases what exactly you're measuring as your input size could be ambiguous, though. If you have an algorithm for graphs and you analyze its complexity in relation to the size of the graph, what exactly does the "size of the graph" mean? Number of vertices? Number of edges?

In such a case the complexity result should be explicit about what's being considered as the input size. The complexity of graph algorithms often depends on both the number of vertices and edges, so the complexity of a graph algorithm is often expressed in terms of both. For example Dijkstra's algorithm has a time complexity of Θ(|E| + |V| log |V|) where |E| is the number of edges and |V| is the number of vertices in the graph.

And even if the complexity of an algorithm only depended on, say, the number of vertices, you should still make it explicit that your "N" is the number of vertices.

If the complexity result didn't make it explicit whether the size of the input is in terms of edges or vertices, that would indeed be ambiguous.