In MySQL 4.1 and above the longest part of recovery after crash for Innodb tables could be UNDO stage – it was happening in foreground and was basically unbound – if you have large enough transaction which needed to be undone this could take long hours.
REDO stage on other hand always could be regulated by size of your Innodb log files so you could have it as large as you like. Read more about it here.
Since MySQL 5.0 the UNDO stage is running in background so it still can be the longest but would not keep server completely unusable (some limitations still apply though).
In the case I’ve been working on recently none of these parts was the longest one.
The server had about 65000 tables using innodb_file_per_table so “InnoDB: Reading tablespace information from the .ibd files…” stage was taking most of the time.
Happily Innodb only needs to scan .ibd files when it was not shut down correctly otherwise restarts would be even more painful.
Even more longest phase has to do with restarts more than crash recovery as it presents in normal restarts as well – “Opening Tables”. As Innodb has to recompute the stats first time it opens the table this can take significant amount of time. Plus worst of all there is serialization in the table cache and only one table can be opened at the time as of MySQL 5.0
It would be great if Innodb would finally optionally store stats, same as MyISAM so one could recompute them in background. Also MySQL should fix things so more than one table can be opened at the same time (though I have not tested if it is still the case with 5.1 which as table_cache code rewritten dramatically)