Expendable rocket design is a local maxima which reduces fitness for reuse. This is because the typical, and traditional, optimizations all work against reuse. Reducing the number of engines on the first stage lowers cost and increases reliability and performance. And makes VTVL operations nearly impossible without adding additional engines (ballooning complexity, increasing stage cost, and reducing performance in an already extremely performance constrained system). Additionally, the traditional method for incrementally improving overall launch vehicle performance is to change the upper stage. By switching to a higher performance LOX/LH2 stage you can increase payload without redesigning the first stage, and without increasing gross liftoff weight. Even with the Falcon 9 they changed the second stage to improve performance, but they avoided the pitfall of making it much more advanced. On paper advanced upper stages seems like smart thing to do. You concentrate your engineering efforts on one of the smaller pieces of the rocket, and you improve performance without necessitating a full redesign. But this results in a vehicle with most of the cost in the upper stage.
This development trajectory leads to a capable launcher, but one that is wholly unsuited for reuse. Reusing the first stage is now extraordinarily difficult, extraordinarily costly, and has little advantage (since most of the cost is in the upper stage anyway). You see the effects of this design pattern in most expendable launchers. Both the Delta IV and Atlas V boosters use a single engine in the first stage, and both use an RL-10 LOX/LH2 engine for the 2nd stage, an extremely expensive engine on its own, let alone when it's integrated into a high-tech stage (such as Lockheed-Martin's legendary Centaur line). The Ariane 5 has gone through 5 different generations of upper stage advancements, and it too has only one engine on its first stage. India's GSLV uses a solid first stage with hypergolic boosters and second stage and a LOX/LH2 3rd stage.
Meanwhile, there hasn't been much pressure on rocket designers to be hard headedly pragmatic. Often times winning government contracts or even private investment meant convincing people of your beyond state-of-the-art designs that would leap frog the competition, rather than rely on common sense engineering and iterative advancements. That's how we got the Shuttle (which was supposed to be about 2 orders of magnitude cheaper to operate than it turned out to be), the X-33/VentureStar program, the NASP/X-30 program, Rotary Rocket, Pioneer Rocketplane, and all the other programs and startups that were cancelled when they ran out of money, ran into engineering problems, or both.
The sensible thing is to try reusing some of the rocket and make the most of that from a cost perspective. Something that saw a bit of attention with the old DC-X program over two decades ago. One problem with that program was that it envisioned a new launcher that was mostly an SSTO, and aimed at building up from small scale rather than building toward reuse from full orbital scale.
The genius of Musk and SpaceX has several facets:
1) Begin with expendable, but design with reuse in mind (high throttle ability in the first stage, most of the costs in the first stage), and work towards there iteratively. That way you get experience in a lot of the most important bits of the business: building orbital rockets, building rocket engines, building spacecraft, launching rockets. And you get cold, hard cash flowing into the company from launches. Cash that keeps the company in business, and finances further innovations.
2) Build reuse not as a different vehicle but as a "feature flag" on a common design. The difference between a reusable launcher and an expendable launcher for SpaceX is a mode selection, not an architectural difference. This means that you get operational testing of the vast majority of your flight hardware for your vehicle with every single expendable launch. This is a well-known risk mitigation strategy in software and other industries, and here it works marvelously. Prior to today's launch SpaceX had 14 previous launches of substantially the same hardware (counting only the v1.1 version).
3) Opportunistically use the first stage after stage sep. for experimenting with boost back and landing. From the very first v1.1 launch SpaceX has been aggressive at testing aspects of the landing and reuse flight mode, equipping stages with landing gear in many cases. This is a fantastic cost saving method as it takes what would be trash and transforms it into test vehicles being operated in typical flight profiles. This takes advantage of hundreds of millions of dollars of flight hardware to conduct an R&D test program on the cheap.
Combine all of that together and you end up with a way to get from A (expendable rockets) to B (reusable rockets) without having to take on a ton of risk, without having to spend insane amounts of money, without having to design and operationally prove a brand new reusable vehicle design, and to build a revenue earning and self-sustaining business before being able to finish reusable vehicle development. It took a significant amount of foresight and savvy to be able to see that route and to execute on it.
And yes, knowing what we know now it would have been easy to do this sort of stuff in the past, more so if we wanted to just throw money at it. But it wasn't obvious until being proven.