One way you can approach this is to use an RS-NOR Latch Array. This is essentially many RS-NOR latches next to each other. RS-NOR latches are circuits that can store a 0 or a 1 (represented in Minecraft as an off or on current). When the button to activate the staircase is pressed, you want all the RS-NOR latches to set themselves, to open the stairs. When the button to close the stairs is pressed, you want to reset the RS-NOR latches to close the stairs.
The good thing about RS-NOR latches is that you can adjust the delay of the signals going to the S (set) and R (reset) lines of the circuit. Essentially, you want to make the lines setting the RS-NOR latches to set them in one order, and the ones reseting the latches to do so in the opposite order.
Unfortunately, it's a little difficult to explain this in text, so I'll point you to this video by Minecraftaddict.
The video isn't about your specific scenario, but to build the station, he uses an RS-NOR latch array. Note how the lines are set through the signal running under the delay, and are reset through the signals that are set to different delays, allowing the pistons to reset correctly.
As promised, here is a little RS-NOR Latch Array tutorial.
This is the RS-NOR Latch Array. It is a series of RS-NOR latches. The nice thing about this design is that the latches are vertical, allowing them to be put next to each other with one block of space in between. Additionally, the reset lines for the latches are underneath, meaning all the latches can easily be reset with one input. The lines running towards the left of the screenshot are the outputs of the latches.
The reset line (or what you'll probably use as the set line) is located under the latches. The signal must be inverted to keep the torches off, so that when an input is given, the line turns off and the torches turn on. I removed part of the right-most latch so the reset could be seen more clearly. Notice the repeaters. Repeaters can pass a signal through blocks, so the reset line signal is sent to a repeater leading into a block, turning the torch on top of the block off, and then sent to a repeater right after the block, which continues until the last latch. This allows one signal to be sent through all the latches to (re)set them from first to last.
This is technically the set line of the latches, but it's better for the reset line when you need the reset to happen in a specific order. This is where you would make adjustments via repeaters make sure the pistons reset in the right order. Note that the final block leading into the latches should always be a repeater, or else the !output signal will contaminate the rest of the line.
That structure in the distance is a piston-powered vertical item transportation system - just ignore it.
Best Answer
The NOT gate also called inverter delays the time exact one tick.
from the minecraft gamepedia
That means the signal on the otherside is one tick to fast. To solve that simply put a repeater in the connection to the other piston.
A repeater also delays the signal with one tick.
from the minecraft gamepedia
That means your circuit should look like this:
I only have the ability to check that with my eyes and ears and it seems pretty at the same time. Anyway you said you tried that...
Here is your secound answer:
There is a thing called instant inverter. It looks like this:
To get the whole thing working remove your inverter and place this instant inverter at this place. Keep in mind that the piston with the inverter acts strange. But this does not influence the block movememt. Neiter from a normal or sticky piston.
from the minecraft gamepedia
You find other instant inverter possibilitys in the source link above.