--- Quote Start ---
Historically, how long would it take for a new Altera FPGA to be widely available from the time it is released?
--- Quote End ---
Time from anouncement to time of delivery is varying, I suppose it depends on what the competition is doing. I think Cyclone IV was a quite early announcement because of Spartan VI.
However, from my experience Altera was always pretty good in meeting the announced schedule. I would not dare to say this about Xilinx. Of course, new parts are always a little bit of risk and you should have close contact with a FAE and order early.