Let's answer the analogous question in 2D because it's a lot easier to visualize! Consider $f = - \log r$, which has $\nabla^2 f = 0$ in 2D.
In image 1, I've plotted a (rescaled) $f$ with the lines of constant $r,\theta$ drawn on. What you are imagining is that as you go down the $r$ curve, you have non-zero second derivative because it's bending, and that you can ignore the $\theta$ direction because it's completely flat that way:
But this isn't really what the Laplacian derivatives are measuring. In image two I've plotted the same curve but with lines of constant $x,y$ drawn on:
Now it's clear that whilst in the $x$ direction (along the nearer side), the function is bending upwards gradually, we can see by the contours that in the $y$ direction (away from us) it is currently bending downwards. And on average, as you say, nothing is happening. Hence $\nabla^2 f = 0$ can make sense: $\partial_x^2 > 0,\partial_y^2 < 0$.
The mathematical way that we capture the relationship between these two diagrams is by converting between derivatives in one coordinate system ($x,y$) to those in another one ($r,\theta$). In this way, we capture all the subtleties of measuring things in different directions in simple formulae, like
$$\nabla^2 f = \frac{\partial^2 f}{\partial r^2} + \boxed{\frac 1 r \frac{\partial f}{\partial r}} + \frac 1 {r^2} \frac{\partial^2 f}{\partial \theta^2}$$
The highlighted term here tells you that if a function has a non-zero slope in $r$, then there's secretly some extra curvature other than that from looking in the increasing $r$ direction: this is due to motion in the direction orthogonal to $r$, and it is because if you look orthogonal to increasing $r$ you're actually still looking at points where $r$ is larger! This is just saying that the tangent to a circle passes through points of increasing distance from the centre of the circle. As a result, because the function $f$ is smaller at larger $r$, we measure a negative curvature as we look in that orthogonal direction, and this contributes to $\nabla^2$.
Hope that helps!
Edit: Notice that if we write $r= \sqrt{x^2+y^2}$ and $\theta = \tan^{-1}(y/x)$ and take $f$ to be only a function of $r$ then
$$\frac{\partial f}{\partial x} = \frac{\partial r}{\partial x}\frac{\partial f}{\partial r} + \frac{\partial \theta}{\partial x}\frac{\partial f}{\partial \theta} = \frac x r f'(r)$$
so
$$\frac{\partial^2 f}{\partial x^2} = \frac{x^2}{r^2} f''(r) + \frac{y^2}{r^3} f'(r)$$
Hence if we are moving along the $x$ axis ($y=0$) then
$$\left[\frac{\partial^2 f}{\partial x^2} \right]_{y=0} = f''(r)$$
But similarly
$$\frac{\partial^2 f}{\partial y^2} = \frac{y^2}{r^2} f''(r) + \frac{x^2}{r^3} f'(r)$$
$$\left[\frac{\partial^2 f}{\partial y^2} \right]_{y=0} = \frac{1}{r} f'(r)$$
This shows that it is the bending in the $y$ direction (which is what is locally orthogonal to the $r$ direction) which gives the extra highlighted term. Meanwhile, the bending in the $x$ direction only gives the naively expected two $r$ derivative term.
Edit: To address Ian's question in the comments - one reason why you actually get exactly zero for these choices of $f$ ($\log$ in 2D, $1/r$ in 3D, ...) is the following, based around the divergence theorem which says that $$\int_V \nabla^2 f \ \mathrm{d} V = \int_{\partial V} \nabla f \cdot \ \mathrm{d} S$$ or in more intuitive words, the Laplacian represents a measurement of whether or not on average $\nabla f$ points in or out of the region $V$.
Suppose you are given a point $\mathbf{x}_0$. Consider a very thin spherical shell at $|\mathbf{x}_0| \pm \delta$ from the origin. Clearly the Laplacian should be the same everywhere in that shell, so it would be sufficient to show that the integral over the shell of the Laplacian vanishes for all sufficiently small $ \delta$.
But by the above theorem, this is the same as making the flux of $\nabla f$ through the shell vanish. Since $$\nabla f \cdot \pm \hat{\mathbf{r}} = \pm f'(r)$$ and since the surface areas of each boundary of the shell are proportional to $r^{d-1}$ in $d$ dimensions, we need $f' \sim r^{1-d}$ in order to obtain a vanishing result.
I.e. in two dimensions, $f' \sim 1/r$ and $f \sim \log r$ or in at least three dimensions, $f \sim r^{2-d}$.
