I like to think about it in the context of the Lorentz Force, i.e. the force on a charged particle by an electric and a magnetic field. The first time you check by yourself that the magnetic force does no work, it is puzzling.
$$\vec F = \vec F_{electric} + \vec F_{magnetic} = (q\vec E) + (q\vec v \times \vec B) $$
The force due to the electric field $q\vec E$ is easy to understand. But, since the result of the cross product $q\vec v \times \vec B$ is always perpendicular to the velocity $\vec v$, then the force due to the magnetic field does zero work (the instantaneous displacement $d \vec r$ is parallel to $\vec v$, therefore $dW = \vec F_{magnetic} d \vec r = 0$).
A good way for students to intuitively understand this, consists on thinking of the charged particle as a car. Then, the electric force is the result of the forward push due to the engine, and the magnetic force is simply the result of the driver inside the car effortlessly turning the steering wheel. That may give you some intuition about it, specially if you consider a vehicle with rear-wheel drive.
No matter how heavy a car or a lorry may be, it is nearly effortless for an old lady to turn the wheel to the right or left, and the whole vehicle will change its trajectory. The work is done by the petrol engine pushing forward. Turning the steering wheel is effortless, but it has a deep impact on the trajectory of the vehicle (the electromechanical steering boost mechanism is there only to counteract internal friction forces).
How can you effortlessly change the trajectory of a heavy lorry? Because the reaction on the turned wheels results in a force that is perpendicular to the movement of the vehicle, therefore it does zero work: it is effortless for the driver. This is easier to understand, as said, if you think on a rear-wheel drive car, so that the front wheels play a passive role in the "push" done by the engine.