It's interesting that NASA, despite working on control algorithms, apparently didn't consider using them for building a reusable rocket. (SLS isn't planned to do a propulsive landing, and neither was its predecessor Ares V.) Though they probably did use them to some extent for the "sky crane": https://en.wikipedia.org/wiki/Sky_crane_(landing_system)
Making any kind of a rocket that works is already nontrivial (once one goes beyond Estes models), but in terms of complexity of the challenge, making some kind of a hopper that goes up and down is a task that ambitious amateur groups with a few members and under $1M in funding were demonstrating even before SpaceX was founded. There is no need for a highly efficient engine, there is no need for lightweight structures. Many other concerns, such as low frequency structure oscillations, aerodynamics, etc are practically nonexistent.
Making a space launch vehicle is a task for a group with at least x100 more resources and experience. Reaching orbital velocity is pretty hard. Most startups do not succeed.
Making a space launch vehicle which does not spend the fuel entirely, while carrying extra hardware to also land after the launch is another step up in how hard this is. Very serious institutions worked on this problem since 1970s but lots and lots of people were skeptical. Shuttle was impressive, but also very expensive. Then SpaceX has shown that it was not only possible, but even practical to make ordinary rockets reusable. That was amazing. Even now, almost a decade later, nobody has shown anything like that -- though a number of Chinese startups are working on it.
