Intuition - why does the period not depend on the amplitude in a pendulum?

The higher you are, the greater the maximum velocity and maximum potential energy.

Consider one pendulum lifted higher than a second both released at the same time. When the higher pendulum reaches the starting point of the second, it already has a velocity greater than 0.

This higher velocity allows the higher pendulum to complete its swing in the same amount of time as the lower, even though it has a longer path.

Since I'm at a computer now I will address a majority of what is said in the comments. For starters, this does not exactly apply to pendulum; only approximately, and the approximation gets worse as $\theta$ increases.

A good way to visualize this is through the Tautochrone curve which is a frictionless curve where for all heights, the time to fall is the same (this is the equivalent of a pendulum period if you ignore the backswing, or have 2 of these curves mirrored; which will be a perfect mirror of the front swing if energy is conserved in the system).

In this scenario, the accelerations work out perfectly (under the same gravity) so that they all arrive at the same time. This is unlike the circular motion, which is only approximately correct for small angles. The interesting thing to note is that looking at a small displacement of a tautochrone curve; it looks approximately circular if you only look at a small section near the bottom. This is an intuitive way to explain why a circular pendulum approximately has this behaviour with small angles.

(Henning mentioned a tautochrone curve in his answer as well. It seemed to be an appropriate way to add more intuition to this)

Hand-wavy intuition: Suppose we don't know about pendulums but want to construct a one-dimensional path, such that a point mass constrained to this path can oscillate around a low point with different amplitudes but constant period.

We do this from the bottom up -- so imagine that we have constructed the path from an altitude of $h_1$ down to $0$ and back up to $h_1$ on the other side. Now we want to extend that up to a sligher higher altitude $h_2$.

When we release our point mass at $h_2$, we can compute what its kinetic energy (and therefore its speed) will be at any altitude, so we can (at least in principle) compute how long it takes it to pass by the already made $h_1$-to-$h_1$ segment. This will be less time than our desired period, and half of the remaining time will be how long the point mass should take to move from $h_2$ to $h_1$. If that is sufficient time (that is, more than it would take the mass to fall straight down from $h_2$ to $h_1$), we can adjust how long time it takes, simply by making the section from $h_2$ to $h_1$ a suitably inclined plane.

Taking this process to the limit (where $h_2$ is just infinitesimally higher than $h_1$) we get some horrendous continuous-delay differential equation that I don't care to either derive in detail or solve -- but Huygens did it in 1659 and found that the solution is an inverted cycloid.

So if we have a bob gliding frictionlessly along a cycloid, it will indeed have the same period for any amplitude.

A pendulum, of course, swings in a circle rather than a cycloid -- but the cycloid turns out to be smooth enough (with nonzero but finite curvature) at the bottom that it can be approximated by a circle. This approximation is good enough that the difference in period between the circle and cycloid go to $0$ as the amplitude goes to $0$.

For small angular displacements, the pendulum differential equation is effectively linear and as such, the amplitude of the oscillation must be independent of the period. Why?

For a linear system, if $x_1(t)$ and $x_2(t)$ are two independent solutions, then $x_3(t) = a_1x_1(t) + a_2x_2(t)$ is also a solution (superposition property).

And so, if a linearized pendulum has a sinusoidal solution $x_1(t) = \cos(\omega_0 t + \phi_0)$, then $A\cos(\omega_0 t + \phi_0)$ is also a solution by the superposition property.