Yes for sure VPNs and firewalls are complementary technologies and both are required on most networks. To simplify you could acquire a UTM box that could offer you all this on the same hardware unit, resulting in reducted TCO.
Leased lines vs. other medium discussion is not about the 'better' or worse. You have to balance between reliability/availability and COST. A properly desgined MPLS VPN (ISP) could offer a pretty decent uptime (just make sure you have an appropriate SLA with the ISP).
Please rate if helpful.
Regards
Farrukh