I don't think the LM7805 has much PSRR left by the time you
get to 10MHz. There should be a curve in the back of the
datasheet, or app notes. As a rule, you want to fix the HF
PSRR problem with a LC network on the incoming supply.
More bulk capacitance does this in a sense, but only using the
"stray" inductance of the feed and if you're not choosy about
capacitor details, perhaps using a cap with too high an ESL to
be effective at the higher frequencies where you need it most.
The other thing about the automitive environment is, ground !=
ground !=ground as you wander around the chassis sheet
metal, engine block, PCM. Only clean, tight, close-in connectiions
make the grounds "close enough" - close enough for uV, I doubt.
Using sheet metal ground is a bad idea, a star ground
with independent conductor is going to be better (but you may
also want to look at fixing whatever the sensor ground is,
or at least running your IA input reference to the same point
to eliminate ground loops.
Similarly relay power and ground ought not involve the signal
conditioning power/ground at all. Coil driver ground wants a
separate conductor and no board connection between them,
cross the ground domain with "digital" signals at minimal
current where you can.