Sufficient conditions for $x, Ax, A^2x, ...$ being linearly indepedent

A possible sufficient condition is that the characteristic polynomial of $A$ is irreducible and $x\ne0$. Unfortunately, with base field $\Bbb R$, we cannot have irreducibility if $n>2$.

By the Popov-Belovich-Hautus (PBH) test in control theory, $x,\,Ax,\,\cdots,\,A^{n-1}x$ are linearly independent if and only if the augmented matrix $[A-\lambda I|x]$ has rank $n$ for every complex eigenvalue $\lambda$ of $A$.

If the characteristic polynomial of $A$ has no repeated roots, then we have a basis $\{v_i\mid 1\leq i \leq n\}$ of eigenvectors for $\mathbb C^n$, and we can express $x=\sum \alpha_i v_i$ in terms of the basis. If all of the $\alpha_i$ are non-zero, then all of your vectors will be linearly independent. In fact, with this condition on $A$, this is a necessary and sufficient condition on $x$.

Here is a quick proof. Let $\lambda_i$ be the eigenvalues, $v_i$ the eigenvectors, and $f(x)$ the characteristic polynomial of $A$. Let $g_i(x)=f(x)/(x-\lambda_i)=\prod_{j\neq i} (x-\lambda_j)$, and let $h_i(x)=g_i(x)/g_i(\lambda_i)$. Then one can check that $h_i(A)v_j=\delta_{ij}v_j$. If $x=\sum a_i v_i$, then $h_j(A)(x)=a_j v_j$, so each eigenvector is a linear combination of $x, Ax, A^2x, \ldots$. Since the eigenvectors are linearly independent, this shows that $\dim \operatorname{Span}(x,Ax,\ldots A^{n-1}x)=n$. On the other hand, if we could write $x$ as a linear combination of some subset of the eigenvectors, then $A^kx$ would also be a linear combination of that same subset, so $\dim \operatorname{Span}(x,Ax,\ldots A^{n-1}x)<n$.

If $A$ has an eigenvalue with geometric multiplicity greater than $1$, then no $x$ will work. Indeed, $\dim \operatorname{Span}(x,Ax,A^2x,\ldots)\leq \dim \operatorname{Span}(I,A,A^2,\ldots)$ which is the degree of the minimal polynomial of $A$. So a necessary condition is that the minimal polynomial equals the characteristic polynomial, which prevents $A$ from having geometric multiplicity greater than $1$ for any eigenvalue.

If $A$ has repeated eigenvalues but all eigenvalues have geometric multiplicity of $1$, then it is still possible to find such an $x$, but things are a bit more complicated. If $A$ is in JNF, then each block has a generator, and if we express $x$ with respect to the basis for the JNF, we need the coefficients of all the block generators to be non-zero. Explaining this is a bit involved, though.