Electrical – Ultra low noise +/-15V power supply

You'll need a switcher to pump up the input voltage, and have it followed by a linear regulator, like Russell proposes. His TPS717xx, however, while having a high PSRR doesn't have a high output current (150mA). High current and high PSRR don't go together well on LDOs. Nevertheless, an LDO may be required, since the 2-4V input volatge suggests that you're powering from batteries, and then you don't want to lose too much power in regulators.
A solution for the PSRR may be to use 2 LDOs in cascade, so that the PSRRs add.
The LP3878-ADJ may be a good choice for your second stage; it's low-noise, can supply 800mA and has an adjustable output which can be set to 5V.
For the preceding stage you could use an LP38690-ADJ. The datasheet shows how you can improve ripple rejection at higher frequencies if you place a 100\$\mu\$F output cap. Caps between each stage (100\$\mu\$F + 10\$\mu\$F + 1\$\mu\$F) are a must, but \$\pi\$-filters are a better idea: caps + ferrite bead + caps. Those should suppress the higher frequencies generated by the switcher.

edit (re your update)
Dave rightly has second thoughts on your using AA batteries, but it's even worse than he calculated. I estimate that you'll need 7V from the switcher to feed the cascaded LDOs, so 600mA @ 7V is 4.2W, at a conversion efficiency of 80% that's 5.25W from the batteries. Two AA cells deliver 3V, so that's 1.75A from the batteries! Not only won't they last long, they won't like it either. I suggest you use a LiPo cell, which delivers 3.7V with a boost regulator, or even two cells in series, giving 7.4V, and use just the LP3878-ADJ. (If you don't use a switcher you don't need the second LDO to suppress its ripple.)

That there is no output start-up spike with the preregulator in place will be because the soft-start of the LM5118 adds tens of milliseconds to the time allowed for the bias to come up and actively control the gate of Q1. That's a pretty reasonable way to have a more controlled start. But let's set that aside to look at some of the other things that can happen during start up.

Start-up power sequencing is always a big concern with any power supply. Things can get quite involved, making sure that proper bias is present at the right time. Here are some common causes of overshoot on start up, in rough order of prevalence:

1. Integrator wind up. A precharge occurs on the integrator capacitor at start, causing a hard start.

2. Uncontrolled start of \$V_{\text{Ref}}\$. A unit step start of \$V_{\text{Ref}}\$ can cause an overshoot of output voltage.

3. Local bias voltage coming up late, or unbalanced start. Unbalanced start of bias can happen when there is bipolar bias voltage. Either the positive or negative output can come up first, in which case the output can rail.

4. Lack of termination at startup. If the output is unloaded at start, the output can overshoot and stay at an excessive level for an extended period.

All of these causes should be checked. Integrator wind up and controlled start of \$V_{\text{Ref}}\$ always have to be managed, and will get further attention here. Local bias sequencing and balance can take many forms and is hard to say much about specifically, but now that the local bias schematic has been added to the question, it is somewhat doubtful that any imbalance or delay would be severe enough to cause overshoot. Lack of termination is usually not a significant factor in a linear supply, but could make any existing overshoot more severe.

Integrator Wind Up

Without an active loop, such as under start up conditions, an integrator capacitor will always become excessively charged. High gain and any offset voltage or input bias currents of the OpAmp will combine to make this so. Then when the loop becomes active, the error amplifier is railed and the supply output overshoots. All practical integrator circuits used in power supplies have some means added to constrain charge up of the integrator capacitor. Quite common is placing a diode in parallel with the capacitor.

Here, \$D_{\text{Lim}}\$ is configured such that if the output of the amplifier should normally be higher than \$V_{\text{Ref}}\$, the amplifier will behave as an integrator. But, for output voltages lower than \$V_{\text{Ref}}\$ no excess charge up of \$C_9\$ will occur and the amplifier will only have unity gain. So, the amplifier can not end up railed to the negative bias voltage. No or minimal overshoot. In the case that amplifier output should be lower than \$V_{\text{Ref}}\$ during normal loop operation, \$D_{\text{Lim}}\$ connection can be reversed to prevent railing to the positive bias supply rail.

Sometimes using a diode is not restrictive enough, especially if \$V_{\text{Ref}}\$ is adjustable over a wide range. In this case a normally closed single pole single throw (NC SPST) analog switch can be used in place of \$D_{\text{Lim}}\$ to make the error amplifier have unity or some proportional gain during start up. At the proper time the analog switch is opened and the error amplifier becomes an integrator again. No overshoot.

Uncontrolled Start of \$V_{\text{Ref}}\$

An abrupt step in \$V_{\text{Ref}}\$ can cause overshoot or ringing at the output. Although this happens a lot at start up, it's not strictly a start up problem. A control loop with inadequate phase margin, anything less than about 68 degrees, will overshoot or ring with a step of \$V_{\text{Ref}}\$. Best way to handle this in general is to design the loop to have adequate phase margin. Best practice at start up is to initiate start with \$V_{\text{Ref}}\$ at zero setting and then ramp to the desired setting over a period of milliseconds.

Note: Initially it appeared that overshoot cause could be delay of local bias. Here is a test to verify and a possible solution offered.

Since it is crucial with this power stage to have active pull-down on Q1-G to maintain control of Q1-S, a crude pre-bias could be applied to Q3-B. A 50kOhm resistor, here shown as \$R_{\text{ff}}\$, could be connected from Q3-B to Q1-D. When voltage appears at Q1-D, Q3 would be turned on actively pulling down Q1-G. To make this work, D6 and D7 would have to be turned around, anodes tied together and R8, and D7-C to IC1A-1, and D6-C to IC2A-1 to allow Q3-B to be pulled down during regulation. This might be the simplest thing to do.

When \$R_{\text{ff}}\$ is not present, ripple rejection of the stage, open loop with \$D_7\$ cathode pulled low, is zero dB.

With \$R_{\text{ff}}\$ in place ripple rejection improved to 20dB. 50kOhm was chosen on a wim, and no effort was made to find a better value.