The GSM shield requires 5v @ 1.5A? Really?
I would use an unregulated PSU for the solenoids, because there's not likely to be any good reason to worry about the exact voltage going through a coil. Same for the relays. As long as it's rectified and filtered to remove any serious ripple, they should be perfectly happy. A simple transistor (and protection diodes) to fire them would suffice.
That leaves the control circuitry and the GSM module. At a load of 1.5A, you really need to move to switching regulators. That's way, way too much current to stick with linear. You'll be generating a TON of heat. That means, you're wasting quite a bit of power, and you need sufficient means to remove that heat. Those LM78xx chips say they'll drive 1.5A, but don't even think about asking them to do it IRL.