Why does Trapezoidal Rule have potential error greater than Midpoint? I can approximate the area beneath a curve using the Midpoint and Trapezoidal methods, with errors such that:
$Error_m \leq \frac{k(b-a)^3}{24n^2}$ and $Error_T \leq \frac{k(b-a)^3}{12n^2}$.
Doesn't this suggest that the Midpoint Method is twice as accurate as the Trapezoidal Method?

Will Orrick's great answer shows why if the function is concave up, then the trapezoid rule overestimates the integral and the midpoint rule underestimates it, and vice versa if the function is concave down. This gives a heuristic explanation for why the errors have opposite signs. But as he points out, it still isn't clear why the max midpoint error is smaller in magnitude.
To see intuitively why this is the case, we can add some more lines to his diagram:

The thick blue curve is the function to be integrated, the upper diagonal line is the top of the trapezoid from the trapezoidal rule, and the bottom diagonal line (which is tangent to the blue curve) is the top of the trapezoid with the same area as the rectangle given by the midpoint rule. The area of the blue shaded region is the error $E_T$ from the trapezoidal rule, and the area of the orange shaded region is (the absolute value of) the error $E_M$ from the midpoint rule. The middle diagonal lines connect the endpoints of the function's curve and its horizontal midpoint.
The entire shaded region is yet another trapezoid (the top and bottom sides are not quite parallel in general, but the side sides are). The vertical line running above the midpoint divides it into two sub-trapezoids. Each sub-trapezoid's diagonal divides it into two triangles that aren't quite congruent (because the parallel sides have slightly different lengths), but are very close to congruent if the function is reasonably close to linear over the interval, so these pairs of triangles have approximately equal areas. If the function's curve matched these diagonals, then the two rules would give (almost) equal and opposite errors, but we see from the fact that the curve is always to one side of these diagonals that the blue region has larger area ($E_T$) than the orange region ($E_M$).
We can roughly motivate the factor of 2 difference by noting that if you subtract off the lower large diagonal line (which makes the top line approximately horizontal as well, at this order), then the curve is more or less a parabola whose vertex is the midpoint - and it's a standard fact that over an interval that's symmetric about and tangent to any parabola's vertex, the area on the parabola's concave side is twice the area on its convex side.
This (heuristic) last step assumed that the function is close to parabolic, but it remains true if we consider an arbitrary cubic polynomial as well, because you can treat it as the sum of a quadratic term (to which the previous argument will apply) and a cubic term that vanishes at the endpoints and the midpoint. This cubic piece must be odd about the midpoint, so its integral will vanish and we can reuse the reasoning above from the simpler quadratic case.
