I can do this by replacing one battery at a time, that's no problem
Yes, that's a good idea. Another alternative is to connect both of the new batteries, and then disconnect the old ones. Since the batteries are in parallel, it doesn't matter if you add a new battery (assuming they are in good health), since the supply voltage will be roughly equal.
Should I be worried about spikes when connecting the wires?
Since you are connecting it in parallel, most likely not. Since there's a load on the from the computer, it is possible that the supply voltage raises slightly (due to the new battery being able to supply more current with less voltage sag), but it should never exceed the rated voltage of the battery. With these 12V batteries, I would not worry.
Should I be using something like ferrite beads or diods to protect my stuff?
If some of the equipment causes lots of switching noise (causing voltage spikes or dips), you might want to include a diode to ensure the voltage drop across the supply is always 12V. However, in most cases a battery can act as a diode itself, so you are already technically protecting yourself via the battery.