As requested:
A hint: find for small $b$ the worst cases, the pairs $(a,b)$ which need the most divisions. You need only consider $1<b<a<2b$, of course. You may notice a pattern which pairs are worst for the Euclidean algorithm.
Before jumping into playing with values, will there usually exist an $a$ for every positive integer $b$ that satisfies these worst case run-times, or is it more of a hit or miss if I pick a random $b$ to start testing relevant values of $a$?
Not for every $b$. But for $b$ in a well-known sequence.
Since the answer is found, let's elaborate:
To find the worst cases, we can employ the computer, after all, computing is what it's for:
Simple Haskell code to find worst cases
module Euclidean where
euclideanLength :: Int -> Int -> Int
euclideanLength a b = go 0 a b
where
go l _ 0 = l
go l n d = go (l+1) d (n `rem` d)
worst :: (Int -> Int -> Bool) -> Int -> [(Int,Int,Int)]
worst cmp mx = go 0 2 3
where
go m b a
| b > mx = []
| a == 2*b = go m (b+1) (b+2)
| cmp n m = (n,b,a) : go n b (a+1)
| otherwise = go m b (a+1)
where
n = euclideanLength a b
and when we ask for cases which take at least as long as the longest found so far:
*Euclidean> worst (>=) 50
[(2,2,3),(2,3,4),(3,3,5),(3,4,7),(3,5,7),(4,5,8),(4,7,11),(4,7,12)
,(4,8,11),(5,8,13),(5,11,18),(5,11,19),(5,12,19),(5,13,18),(6,13,21)
,(6,18,29),(6,18,31),(6,19,30),(6,19,31),(6,21,29),(7,21,34),(7,29,47)
,(7,29,50),(7,30,49),(7,31,49),(7,31,50),(7,34,47),(8,34,55),(8,47,76)
,(8,47,81),(8,49,79),(8,49,80),(8,50,79),(8,50,81)]
Hmm, not too obvious (though if you look closely, it is discernible), let's ask for a strictly longer sequence:
*Euclidean> worst (>) 50
[(2,2,3),(3,3,5),(4,5,8),(5,8,13),(6,13,21),(7,21,34),(8,34,55)]
Houston, we have a pattern!
The worst cases are $a = F_{n+1},\; b = F_n$ with the Fibonacci numbers $F_n$.
Now that the worst cases are identified, it remains to
- show that they meet the requirements, and
- understand why they are the worst cases.
Defining the Fibonacci numbers $F_0 = 0,\; F_1 = 1,\; F_{n+2} = F_{n+1} + F_n,\, n \geqslant 0$, we see that $\lambda(F_{n+2}, F_{n+1}) = \lambda(F_{n+1},F_n) + 1$, and since $F_2 = 1$ needs one division, we have $\lambda(F_{n+1},F_n) = n-1$.
We want to show that
$$\frac{\log F_n}{\log \phi} \leqslant n-1 \leqslant \frac{\log F_n}{\log \phi} + 1,$$
or
$$(n-2)\log \phi \leqslant \log F_n \leqslant (n-1)\log \phi.$$
With Binet's formula, exponentiating that yields
$$\begin{align}
\phi^{n-2} &\leqslant \frac{\phi^n - \psi^n}{\phi-\psi} \leqslant \phi^{n-1}\\
\iff \phi^{n-1} + \phi^{n-3} &\leqslant \phi^n - \psi^n \leqslant \phi^n + \phi^{n-2}
\end{align}$$
since $\phi\cdot\psi = -1$. Using $\phi - 1 = \frac1\phi$, the left inequality becomes
$$\psi^n \leqslant \phi^{n-1}(\phi - 1) - \phi^{n-3} = \phi^{n-2}-\phi^{n-3} = \phi^{n-4},$$
upon division by $\phi^{n-4}$
$$(-1)^{n-4}\psi^{2n-4} \leqslant 1.$$
That's certainly true for $n \geqslant 2 \iff 2n-4 \geqslant 0$, since $\lvert\psi\rvert < 1$. The right inequality becomes, after subtracting $\phi^n$
$$-\psi^n \leqslant \phi^{n-2},$$
which holds since (for $n\geqslant 2$) we have $\lvert\psi^n\rvert < 1 \leqslant \phi^{n-2}$.
So part 1 is done.
Now, why do we get the longest division chains for successive Fibonacci numbers?
Informally, we want the sequence $r_k$ of remainders to decrease as slowly as possible. If we have a large quotient $q_k = \lfloor r_{k-1}/r_k\rfloor$ in the sequence, then $r_{k+1}$ is much smaller than $r_{k-1}$, which we don't want. So the quotients should be small, ideally all should be $1$ except for the first, which doesn't matter, and the last, which is $r_{\lambda-1}/r_\lambda > 1$.
More formally, we note that the Euclidean algorithm is almost exactly the continued fraction algorithm, the steps
$$\begin{align}
r_{k-1} &= q_kr_k + r_{k+1}\\
r_k &= q_{k+1}r_{k+1} + r_{k+2}
\end{align}$$
become upon division by $r_k$ resp. $r_{k+1}$
$$\begin{align}
\frac{r_{k-1}}{r_k} &= q_k + \frac{r_{k+1}}{r_k}\\
\frac{r_k}{r_{k+1}} &= q_{k+1} + \frac{r_{k+2}}{r_{k+1}}
\end{align}$$
which is the continued fraction algorithm. The sequence of quotients in the Euclidean algorithm for $a$ and $b$ is the sequence of partial quotients in the continued fraction expansion of $\frac{a}{b}$ (the one that does not end with $1$).
Now, if we have a simple continued fraction of length $\lambda$ not ending in $1$,
$$x = [a_0,\, a_1,\, \dotsc,\, a_{\lambda-1}],$$
for the convergents
$$\frac{p_n}{q_n} = [a_0,\,a_1,\, \dotsc,\, a_n],$$
we have the recursion
$$\begin{align}p_{n+1} &= a_{n+1}\cdot p_n + p_{n-1} & q_{n+1} &= a_{n+1}\cdot q_n + q_{n-1},\end{align}$$
starting with $p_{-2} = 0,\, p_{-1} = 1,\, q_{-2} = 1,\, q_{-1} = 0$.
We are only interested in the denominators $q_n$, for which we see $q_0 = a_0\cdot q_{-1} + q_{-2} = 1$, $q_1 = a_1\cdot q_0 + q_{-1} = a_1$, and from the recursion $q_{n+1} = a_{n+1}q_n + q_{n-1}$, it is clear that $a_0$ has no influence on $q_n$, and the denominator $q_{\lambda-1}$ will be minimal if $a_1 = a_2 = \dotsc = a_{\lambda-2} = 1$ and $a_{\lambda-1} = 2$.
Choosing $a_0 = 1$, we find the convergents
$$\frac{p_0}{q_0}=\frac11,\, \frac{p_1}{q_1}=\frac21,\, \frac{p_2}{q_2}=\frac32,\, \dotsc,\,\frac{p_n}{q_n} = \frac{F_{n+2}}{F_{n+1}},\, \dotsc,\, \frac{p_{\lambda-2}}{q_{\lambda-2}}=\frac{F_{\lambda}}{F_{\lambda-1}},\, \frac{p_{\lambda-1}}{q_{\lambda-1}} = \frac{F_{\lambda+2}}{F_{\lambda+1}}$$
and thus that $F_{\lambda+1}$ is indeed the smallest $b$ for which the Euclidean algorithm can take $\lambda$ divisions.
Best Answer
This is how we can relate logarithms to numbers of digits:
Claim. For $n$ a positive integer, let $d$ be the number of digits of $n$ in base $B$. Then $d-1 \le \color{blue}{\log_B(n) < d}$.
For example, in base $B=10$, any $4$-digit number $n$ satisfies $1000 \le n < 10000$, so $3 = \log_{10}(1000) \le \log_{10} n < \log_{10}(10000) = 4$.
Proof. If $n$ has $d$ digits in base $B$, then (since the $d$th place has value $B^{d-1}$) we must have $B^{d-1} \le n < B^d$. Taking logarithms, and noting that $\log_B$ is an increasing function, we get $d-1 \le \log_B(n) < d$. $\Rule{1ex}{1ex}{0pt}$
So if you have proved that the Euclidean algorithm terminates in at most $2 \log_2(b)$ steps, then we also have the fact that $\color{blue}{\log_{10}(b) < d}$, where $d$ is the number of (base-$10$) digits of $b$. So, the number of steps is at most $2 \log_2(b) = 2 \log_2(10) \log_{10}(b) < 2 \log_2(10) d \approx 6.64d$.