I think it may help to start looking at the other direction. What would happen if you made the Saturn V bigger? Let's go back to April 30, 1968, on the floor of the Senate.

Dr. von Braun: I think there is evidence that the Russians are working on a rocket larger than the Saturn V. [...]

Senator Cannon: Would you care to speculate as to why they may be attempting to get a first-stage capability greater than the Saturn V?

Dr. von Braun: Sir, I believe -- for anyone who believes that space is here to stay, it is pretty obvious that large payload capability is a key to any major space operation, particularly if a nation wants to use men in space. You just need plenty of payload to make a manned operation in space useful and attractive. [...]

Senator Cannon: Of course, on Apollo now, we have got to the point where there is very little leeway in the payload capability because of the growth in the Apollo capsule weight requirements. [...]

So, bigger means more payload, which means you can carry more into space.

Having too much payload capacity wasn't really a common problem with historical spaceflight. For example, the Mercury project was using Atlas rockets with a 2000 pound specified limit for the capsule, yet the original design put the capsule at 2400 pounds. (Fortunately, plus or minus 25 percent, but it meant they were shooting for the minimum and skating on the edge.)

For Saturn V, on later missions, instead of cutting back, they upgraded the payload capacity. That's not consistent with the idea of somehow having too much.

The only thing I can think that's related is how the early Saturn program wasn't with NASA at all -- it was with the Army Ballistic Missile Agency, and the Army was thinking of connecting the Saturn to already-existing missiles. This essentially limited the design potential of the Saturn and was described as "considering the purchase of a 5-ton truck for hauling a heavy load and finally deciding to merely load a wheelbarrow full of dirt." Fortunately, the Army lost interest in the idea and the ABMA group got moved to NASA, where the full potential of the Saturn was realized by the directive to go to the moon.

...

Sources:

Bilstein, R (1996). Stages to Saturn: A Technological History of the Apollo/Saturn Launch Vehicles. NASA History Office.

Logsdon, J. and Launius, R. (ed) (2008). Explroing the Unknown: Selected Documents in the History of the U.S. Civil Space Program. Nasa History Office.

U.S. Congress Senate Committee on Aeronautical and Space Sciences, Hearings.

The history of NASA's moon rocket is a complicated one, and it was not the case that the Saturn V was designed from the start to be that rocket. Indeed, nothing like the Saturn V would have had the lift capability to launch the Apollo lunar mission stack that was initially planned. Which is why early on the plan was to develop a super heavy lift launcher called "Nova" (specifically the Nova C-8 configuration), with the ability to put up to 75 tonnes into a trans lunar injection (TLI) trajectory.

They needed such an enormous payload because originally the plan was for a "direct ascent" mission profile, which would involve the entire crewed spacecraft landing on the surface of the Moon and taking off to return to Earth. The alternative competing mission profile was Earth Orbit Rendezvous (EOR), the assembly of a massive multi-part spacecraft in Earth orbit using primarily Saturn C-2 (and later C-3) launches (configurations that were never built). These choices were later surpassed by a third choice: a lunar orbit rendezvous profile with a separate CSM and LM, at great weight savings but at the time seemingly risky due to discomfort with making orbital rendezvous at the Moon a mission critical step, though those fears eased as project Gemini provided an opportunity to get acquainted with orbital rendezvous.

As work on the Apollo spacecraft design was occurring and funneling down to a final version launch vehicle development was also occurring in parallel. Of note, in late 1961 the Saturn C-4 had been funded and was initially intended to put the EOR direct ascent Apollo hardware into orbit in just two launches, instead of the many more that the C-3 or C-2 would have required. In 1962 NASA decided to change its mind on the C-4 and wanted to add an extra engine on the first stage, increasing its payload capability. This new C-5 configuration didn't require an entire redesign of the vehicle due to the conservatism of Von Braun's design bureau. They were able to add another F-1 engine at the junction of the cross-beams used to mount the other 4 engines, which turned out to have some beneficial effects in other ways (in addition to increased payload) though did also introduce more severe consequences to the POGO oscillation problem, which almost resulted in the loss of a vehicle on a few occasions (including during the Apollo 13 launch). The C-4 had only ever been intended to be an intermediate step on the way to the C-8, but with the addition of the extra engine to become the C-5 and the high performance levels seen coming out of the F-1 and other engines in development meant that it ended up having nearly as much payload capacity as the lower ranges of the initial Nova C-8 designs. By the time the Apollo hardware design was "finalized" (in a Design_FINAL_(FINAL)_FINALFINAL_2.pdf sort of way) the Saturn C-5 (instead of the C-8) was selected as the launch vehicle, and renamed the Saturn V. And this "extra performance" of the Saturn C-4/C-5 may be the source of various stories about Von Braun sandbagging the payload figures as a hedge against weight growth of the Apollo hardware.

Ultimately, the Nova C-8 was never built as the Apollo hardware using the LOR profile was sufficiently light enough to be able to make trips to the Moon and back on just a single Saturn V launch. Over the course of the Apollo Program many various efficiencies and ways of nudging up performance were found. These enabled the "J-class" missions (Apollo 15, 16, and 17) with extended duration lunar stays and using the Lunar Roving Vehicle.

As for the comparison to the Falcon Heavy, it's not really apt as it has less than half of the Saturn V's payload to LEO and an even smaller fraction of its payload to TLI (due to the upper stage engine's lower Isp), so of course it would be a smaller rocket.

Further reading:

• Stages to Saturn by Roger E. Bilstein

I will approach this answer from a more technical, rather than a strictly historical perspective. I will talk more history at the end but i will start with numbers, as that is what i am more familiar with.

The Saturn V is a monster of a rocket. The largest rocket ever built. It is so big that it was able to carry 3 men and another rocket to the moon and back, carrying all the food, air, water, and consumables necessary for an approximately 8 day journey further than anyone else has gone before or since.

Both rockets, the Saturn V and the Falcon Heavy must spend a lot of energy to get going fast enough to get into orbit. Obviously the Saturn V would have to spend more energy to get up there because it is bigger but lets take a comparable comparison point for both of them so that we can compare rocket capabilities. This bench mark is the first stage orbit called Low Earth Orbit (LEO).

The rockets are each designed to carry different payloads to orbit. The Saturn V was capable of lifting 118,000 kg to LEO. While the Falcon heavy is capable of lifting 63,800 kg to LEO.

This establishes the basis of your question. The saturn V was bigger, but was it over engineered and over capable?

Crunching more numbers and googling the Saturn V was able to carry a 41,000 kg payload to the moon. This was the Apollo Command and Service module and the Lunar Module (LM), including the later Lunar Roving Vehicle (LRV).

The Launch mass of the Apollo Command and Service Modules was 28,800 kg including fuel, which was enough to establish a stable orbit and break orbit for a return to earth.

The Landing Module had a launch mass of 16,400 kg and was intended to support 2 men for multiple day excursions on the moon, then launch back up to the Apollo Command module to bring the astronauts home.

There was a little extra fuel for mistakes and corrections, and the unforeseen events, but not much extra fuel because it is expensive. Apollo 13 springs to mind, as well as how Apollo 11 nearly ended in disaster because they could not find an adequate landing zone.

Remember that the Saturn V rocket could carry 41,000 kg to the moon. The Command and Service Module together were 28,800 kg and the LM was 16,400 kg. Together that is 45,200 kg. This means that the Command and Service Module likely had to use it’s engine some to help get to the moon, but it is close to correct.

The Falcon heavy cannot, in a single mission, land people on the moon or any other body except Earth. It would take multiple Falcon heavy launches to do the same thing as one Apollo mission.

In short, the size of the Saturn V does not mean it was over engineered. It was designed specifically for the mission. Any mission for more distant targets or requiring larger payloads would have required a redesign of the Saturn V. These plans did exist. Wernher von Braun was planning on variants that attached boosters to the Saturn V, or other redesigns of the rocket for increased payload to LEO, and beyond.

Now for the historical. There was some over engineering of the rocket, but most of the over engineering that I know of is due to changing design parameters. The Apollo Service module (the tiny rocket part) had an engine that was twice as strong as it needed to be to complete the job. This was because it was originally planned that the entire CSM would land on the moon without the LM. The engine was designed to be able to lift the rocket off of the moon, not just enter and break orbit. Likely, it was too expensive to redesign, so it was kept.

In short, they understood clearly the missions requirements and designed the rocket to safely meet those requirements, no more. To do more would have been more expensive.