The $O(n)$ statement in your original question is true. (For the $O(j)$ statement, see the note at the bottom.)
If $n$ is your parameter defining the size of the system, and $k\ge1$ is another parameter, denote by $X_{n,k}$ the random time it takes the $k$th particle appearing at position 1 to leave the system.
I'm interpreting your question as asking to show that for any value of $k$, $X_{n,k}$ is with asymptotically high probability (as $n\to\infty$, uniformly in $k$) bounded by $C n$ for some constant $C>0$.
Claim. This holds with $C=4$.
For the proof, I will construct two random variables $Y_n$ and $Z_n$ such that
$$
X_{n,k} \preceq Y_n \preceq Z_n, \qquad(*)
$$
(where $\preceq$ denotes stochastic domination), and such that $Z_n$ is a well-understood random variable for which we know (appealing to a famous hydrodynamic limit theorem of Rost) that $Z_n = (4+o(1))n$ asymptotically. Conceptually, what I'm doing is showing that even after changing your system in two ways, each of which slows down the particle at $1$, making it take longer to leave the interval $[1,n]$, even in the slowed down version it still manages to leave in time $O(n)$.
Now let me define $Y_n$ and $Z_n$:
$Y_n$ is the time for the particle in position 1 to leave the system when it is started with the initial condition in which all positions $1,2,\ldots,n$ initially contain a particle.
To define $Z_n$, consider a TASEP on the entire integer lattice $\mathbb{Z}$ started with the initial condition for which all positions $\le n$ contain a particle, and all positions $>n$ are vacant. In this process, let $Z_n$ be the time it takes the particle initially at position $1$ to reach position $n+1$.
The relations $(*)$ are intuitively plausible, and not difficult to justify rigorously. The idea with the claim that $X_{n,k} \preceq Y_n$ is that adding more particles to the initial condition can only slow down the particle at $1$ and make it take longer to leave the system. Formally, the claim that $X_{n,k} \preceq Y_n$ is an easy consequence of the following lemma:
Lemma (monotonicity property). Let $\boldsymbol{\mu}$ and $\boldsymbol{\nu}$ be two initial particle configurations for the system described in the question, with both of them assumed to contain a particle at position $1$, and with the further assumption that
$\boldsymbol{\nu}$ dominates $\boldsymbol{\mu}$, that is,
that in any position where $\boldsymbol{\mu}$ has a particle, $\boldsymbol{\nu}$ also has a particle. Let $T_1$ denote the time it takes the particle in position $1$ to leave the system when the system is started with initial configuration $\boldsymbol{\mu}$, and let $T_2$ denote the time it takes the particle in position $1$ to leave the system when the system is started with initial configuration $\boldsymbol{\nu}$.
Then the random variable $T_2$ stochastically dominates $T_1$.
Proof of the lemma. Couple the two systems by running them with the same family of Poisson clocks governing the "wake-up" times but with the different initial conditions $\boldsymbol{\mu}$, $\boldsymbol{\nu}$. With this coupling, it is easy to check the relation $T_1 \le T_2$ holds pointwise on the probability space (the particle that started at 1 in the first system always lags behind the particle that started at 1 in the second system - follows by induction on the number of wake up events). Therefore the claimed stochastic domination holds. $\blacksquare$
For the proof of the second relation $Y_n \preceq Z_n$, again we need to use a monotonicity argument. I won't spell out the formal details, but the idea is that $Z_n$ is defined similarly to $Y_n$ except on a system in which it is more difficult for particles inside the interval $[1,n]$ to leave that interval - with your original system, particles at $n$ are never blocked when they wake up. So an argument along the same lines of the one used in the proof of the above lemma will show the stochastic domination we need.
Now that we know $(*)$, the final thing to note is that $Z_n$ is defined in terms of a standard version of the TASEP known as the TASEP on $\mathbb{Z}$ with step initial condition - in chapter 4 of my book The Surprising Mathematics of Longest Increasing Subsequences I refer to it as Rost's particle process. (There is only one cosmetic difference, which is that in the usual definition of this process we have particles initially in all positions $\le 0$ instead of all positions $\le n$ as we have here, but it's obvious how to translate between those two versions.) Therefore we can apply the hydrodynamic limit theorem of Rost that explains the asymptotic behavior of this process and in particular gives the asymptotics of $Z_n$. See Theorems 4.20, 4.21, 4.22 in section 4.7 of my book for three equivalent formulations of Rost's result. Each of them implies the $4+o(1)$ claim about the asymptotics of $Z_n$ once the appropriate values for the relevant parameters are plugged in.
Alternatively, one can interpret $Z_n$ in the language of last passage percolation: again using the notation of chapter 4 of my book, we have the equality in distribution
$$
Z_n \stackrel{D}{=} G(n,n),
$$
where $G(i,j)$ are the last passage times defined on page 224. With this interpretation, the claim about the asymptotic behavior of $Z_n$ follows from the combination of Theorem 4.13 on page 233 and Theorem 4.18 on page 244. (More precisely, in equation (4.46), set $x=y=1$ in the formula for $\Psi(x,y)$ to get the constant $4$ that we're claiming.)
To conclude, since $X_{n,k}$ is stochastically dominated by $Z_n$ and $Z_n = (4+o(1))n$ with asymptotically high probability, we get the claim.
Note: in the discussion above I focused on your $O(n)$ claim, but the argument applies equally to the more general $O(j)$ bound for getting to position $j$, as long as $j/n$ is bounded away from $0$. I'll leave that modification as an exercise.
