As Glen_b pointed out, if the buses arrive every $15$ minutes without any uncertainty whatsoever, we know that the maximum possible waiting time is $15$ minutes. If from our part we arrive "at random", we feel that "on average" we will wait half the maximum possible waiting time. And the maximum possible waiting time is here equal to the maximum possible length between two consecutive arrivals. Denote our waiting time $W$ and the maximum length between two consecutive bus arrivals $R$, and we argue that
$$ E(W) = \frac 12 R = \frac {15}{2} = 7.5 \tag{1}$$
and we are right.
But suddenly certainty is taken away from us and we are told that $15$ minutes is now the average length between two bus arrivals. And we fall into the "intuitive thinking trap" and think: "we only need to replace $R$ with its expected value", and we argue
$$ E(W) = \frac 12 E(R) = \frac {15}{2} = 7.5\;\;\; \text{WRONG} \tag{2}$$
A first indication that we are wrong, is that $R$ is not "length between any two consecutive bus-arrivals", it is "maximum length etc". So in any case, we have that $E(R) \neq 15$.
How did we arrive at equation $(1)$? We thought:"waiting time can be from $0$ to $15$ maximum. I arrive with equal probability at any instance, so I "choose" randomly and with equal probability all possible waiting times. Hence half the maximum length between two consecutive bus arrivals is my average waiting time". And we are right.
But by mistakenly inserting the value $15$ in equation $(2)$, it no longer reflects our behavior. With $15$ in place of $E(R)$, equation $(2)$ says "I choose randomly and with equal probability all possible waiting times that are smaller or equal to the average length between two consecutive bus-arrivals" -and here is where our intuitive mistake lies, because, our behavior has not change - so, by arriving randomly uniformly, we in reality still "choose randomly and with equal probability" all possible waiting times - but "all possible waiting times" is not captured by $15$ - we have forgotten the right tail of the distribution of lengths between two consecutive bus-arrivals.
So perhaps, we should calculate the expected value of the maximum length between any two consecutive bus arrivals, is this the correct solution?
Yes it could be, but : the specific "paradox" goes hand-in-hand with a specific stochastic assumption: that bus-arrivals are modeled by the benchmark Poisson process, which means that as a consequence we assume that the time-length between any two consecutive bus-arrivals follows an Exponential distribution. Denote $\ell$ that length, and we have that
$$f_{\ell}(\ell) = \lambda e^{-\lambda \ell},\;\; \lambda = 1/15,\;\; E(\ell) = 15$$
This is approximate of course, since the Exponential distribution has unbounded support from the right, meaning that strictly speaking "all possible waiting times" include, under this modeling assumption, larger and large magnitudes up to and "including" infinity, but with vanishing probability.
But wait, the Exponential is memoryless: no matter at what point in time we will arrive, we face the same random variable, irrespective of what has gone before.
Given this stochastic/distributional assumption, any point in time is part of an "interval between two consecutive bus-arrivals" whose length is described by the same probability distribution with expected value (not maximum value) $15$: "I am here, I am surrounded by an interval between two bus-arrivals. Some of its length lies in the past and some in the future but I have no way of knowing how much and how much, so the best I can do is ask What is its expected length? -Whichwhich will be my average waiting time?" - And the answer is always "$15$", alas.