For reading multiple inputs I think you will find interrupts are the way to go.
So far it is all rather vague. You haven't posted your attempt to use interrupts, so we can't comment on the method you used.
... the issue I am getting is that when the external triggers are firing at rates of about 500Hz ...
A 16 MHz processor should be able to handle incoming data at 0.5 KHz.
I was able to get speeds that were actually quite acceptable. Once I added back all the necessary conditional logic and modes the timing got too delayed again.
Again, can you give figures please? What speeds? What is "too delayed"?
Maybe sketch the sort of input pulses you are expecting. Are you saying you have 4 x 500 Hz pulses, where they may fire in close proximity? How close? What is an acceptable detection rate?
The analogRead takes around 104 uS, so whether or not you do it infrequently, whenever you do that there is a window of 104 uS when you won't detect anything, especially in a polling loop. It's possible to do analog reads asynchronously.