Expected length of longest construction path in Barabási–Albert Model
(Answer-in-progress, according to comments.)

I will look at a special case, and then discuss how it relates to the general case. The special case is $m=1$ and $V(G)=\{0\}$ with no edge. The added vertices, in order, are $1,2,\ldots,n$, starting from $1$.

Let $d_{i,n}$ be the degree of vertex $i$ divided by $2n$. So $\sum_{i=0}^n d_{i,n}=1$. Let $l_i$ be the length of the longest path from $i$ to $0$ that visits vertices in decreasing order. (Vertices added after $i$ do not affect decreasing paths starting from $i$, so there is no need for $l_{i,n}$.) Both $d_{i,n-1}$ and $l_i$ are random variables. The generating model for these variables is how you'd expect: Once we fixed their values for $n-1$, we pick a number $k_n$ from $\{0,\ldots,n-1\}$ according to the probabilities $d_{i,n-1}$, and compute $d_{i,n}$ and $l_n$ as if we added edge $nk_n$.

We have that $l_n=1+l_{k_n}$, where $k_n$ is a random variable drawn from $\{0,\ldots,n-1\}$ according to the distribution given by $d_{k,n-1}$. In other words, $l_n=1+\sum_{i\lt n}[k_n=i]l_i$ and $\mathbb{E}[l_n]=1+\sum_{i\lt n}d_{i,n}\mathbb{E}[l_i]$. (The independence here is a bit tricky. In the comment on the post I said it does not hold, but I think it does. The trick is to think of this as a stratified generative model, such that the choice of $k_n$ is independent from $l_i$, but drawn from a certain distribution.)

Let's assume, without proof for now, that $d_{i,n}$ depends on $i$ as $\Theta(i^c)$ for some constant $c$.

Now, let's assume $\mathbb{E}[l_n]=O(f(n))$, and see what properties should $f(n)$ have. According to the recurrence on $\mathbb{E}[l_n]$, we should have that
$$
\sum_{i=0}^{n-1} i^c f(i) \Big/ \sum_{i=0}^{n-1} i^c = O(f(n))
$$
In the continuous approximation, this is
$$
\int_1^n x^c f(x) \,dx = O(n^{c+1}\cdot f(n))
$$
One function that has this property is $f(n)=\log n$.

But, does $d_{i,n}$ grow like $i^c$ (for fixed $n$)?

When $m=1$, we can write a recurrence on vertex degrees. The arc $ni$ occurs with probability $d_{i,n-1}$, so $$d_{i,n}=d_{i,n-1}\frac{2(n-1)d_{i,n-1}+1}{2n}+(1-d_{i,n-1})\frac{2(n-1)d_{i,n-1}}{2n}=d_{i,n-1}\Bigl(1-\frac{1}{2n}\Bigr)$$ The border conditions are $d_{n,n}=1/2n$ and $d_{0,1}=d_{1,1}=1$. Now apply linearity of expectation and approximate $\sum_k\log\Bigl(1-\frac{1}{2k}\Bigr)$ with an integral. Alternatively, note that $d_{i,n}/d_{i-1,n}=d_{i,i}/d_{i-1,i}=(i-1)/(i-1/2)$, so $d_{i,n}$ is roughly $\Gamma(n)/\Gamma(n+1/2)$.

Both approaches lead to $\mathbb{E}[d_{i,n}]=\Theta(i^{-(1/2)})$.

For $m=2$, you draw two variables $k_n$ and $k'_n$ from $\{0,\ldots,n-1\}$ according to $d_{i,n}$, and we keep just the maximum. This is like picking just one variable, $\max\{k_n,k'_n\}$, but from a different distribution. The question is if this distribution is still $\Theta(i^c)$ for some (other) $c$. Let $d^{(2)}_{i,n}$ be this distribution. We have, dropping the $n$ subscript, $d^{(2)}_i=2\sum_{j=0}^i d_i d_j + d_i^2$. So, $d^{(2)}_i=\Theta(1/i)$. In fact, $d^{(2m)}_i=2\sum_{j=0}^i d^{(m)}_i d^{(m)}_j + {d^{(m)}_i}^2$. Again based only on some quick-and-dirty calculations, I believe that for $m\gt 2$ we have $d^{(m)}_i=\Theta((\log i)^{cm}/i)$, which would seem to say that the $O(\log n)$ bound on $\mathbb{E}[l_n]$ doesn't work anymore.

The only thing that matters about the seed graph is how many edges it has. I didn't look at how this affects the answer, but, again, it cannot increase the expected length.