septillion:
If I had 16V on my battery I would be very concerned... :
16V in a car, under normal conditions is VERY concerning, you're right. But, I've seen cases where a faulty alternator can push much more than that through.
So, that beg's the question: How does one actually protect a curcuit from over-voltage?
septillion:
You mean non-automotive 12V relays you mean? Because every modest modern (black box) controller in a car has multiple. And now they finally switch to transistors for most. Which I would prefer in most applications as well nowadays.
7805 is indeed not really rated for 24V automotive. And besides that, in a modern jelly bean design you don't want to go linear for that kind of voltages and currents.
I have thought about replacing the relay with a transistor, but from experience, in another field (mobile generators and air compressors), relays tend to last longer than transistors.
septillion:
And you say you want to make hundreds. That tells me two things
a) I don't really think you're up to that if you ask questions like this
Why, cause I'm looking for recommendations on parts, from someone else who already tried a couple different components and know what works, and what doesn't?
As I said before, I can use an of the shelf buck converter. I have 34 spare ones right now (bought a bag of 50 a while ago), but want to keep the design on a single PCB. And, at the same time, I don't know if the LM2596S is the best way to go either.
septillion:
b) I assume you want to sell them and not Open Source then so that's where my help ends. This is a forum for Arduino, an Open Source community. If you want to make money I want in on the profit 
So, building an open source platform and selling it is illegal? Am I not allowed to charge for my time, materials and assembly costs?
If that was the case, you wouldn't even have know about Arduino's!
What I am designing will be open source in the sense that people can change the Arduino sketch. The PCB will have a ISP header with instructions on how to use it to load a new sketch (just hope they don't mess with the boot loaders?)
septillion:
All I can say, look at the different switch mode IC's or modules you supplier can deliver and pick one that suits your needs
And don't forget to follow designer recommendations, to add the proper protection for automotive use and to make prototypes.
Herein lies the problem: There are so many.