Indeed you made one mistake: the infalling observer does not see the outside universe "speed up". Look at what happens in a space-time diagram. At the spacetime point where your astronaut passes the horizon, he can only see what's in his past light cone, and that's the universe at early times only. It's the signals that he sends back (or tries to) that reach the outsine world only at infinite times.
Thus, the observing astronaut sees his black hole as it is long before any evaporation sets in, so his black hole is still there. Now leaving aside some other quantum issues, where opinions aren't completely settled and perhaps even our presently used language could be inapropriate, the observer just continues on, and in a finite amount of time, very quickly unless the black hole were more than millions of times heavier than the sun, he is killed by the central singularity.
In a black hole with high angular momentum (Kerr black hole), the singularity takes the form of a ring along the equator, and the astronaut might try to sail past it safely, and he would be able to enter into a strange new universe where he may or may not leave a negative mass black hole behind him, were it not that debris from other objects that fall in later will kill him before that happens, and while trying to pass a second horizon, he will be killed because that second horizon is unstable.
You need to be a lot more careful when you use the phrase red-shift, due to how frequency is measured in general relativity. Roughly speaking, a photon is characterised by its wave vector $k$, which is a light-like four vector. The frequency measured by an observer is $g(\tau,k)$ where $g$ is the metric tensor, and $\tau$ is the unit vector tangent to the observer's world-line.
A little bit of basic Lorentzian geometry tells you that for any given photon $k$, instantaneously there can be observers seeing that photon with arbitrary high and arbitrarily low frequency.
So: start with your space-time. Fix a point on the event horizon. Fix a photon passing through that space-time event. For any frequency you want to see, you can choose a time-like vector at that space-time event that realises that frequency. Now, since the vector is time-like and the event horizon is null, the geodesic generated by that vector must start from outside the event horizon and crosses inside. Being a geodesic, it represents a free fall. So the conclusion is:
For any frequency you want to see, you can find a free falling observer starting outside of the black hole, such that it crosses the event horizon at the given space-time event and observes the frequency you want him to see.
So you ask, what is this whole business about gravitational red-shift of Schwarzschild black holes? I wrote a longer blog post on this topic some time ago and I won't be as detailed here. But the point is that on the Schwarzschild black holes (and in general, on any spherically symmetric solution of the Einstein's equations), one can break the freedom given by local Lorentz invariance by using the global geometry.
On Schwarzschild we have that the solution is stationary. Hence we can use the time-like Killing vector field* for the time-translation symmetry as a "global ruler" with respect to which to measure the frequency of photons. This is what it is meant by "gravitational redshift" in most textbooks on general relativity (see, e.g. Wald). Note that since we fixed a background ruler, the frequency that is being talked about is different from the frequency "as seen by an arbitrary infalling observer".
(There is another sense in which redshift is often talked about, which involves two infalling observers, one "departing first" with the second "to follow". In this case you again need the time-translation symmetry to make sense of the statement that the second observer "departed from the same spatial point as the first observer, but at a later time.)
It turns out, for general spherically symmetric solutions, there is this thing called a Kodama vector field, which happens to coincide with the Killing vector field on Schwarzschild. Outside of the event horizon, the Kodama vector field is time-like, and hence can be used as a substitute for the global ruler with respect to which to measure red-shift, when the space-time is assumed to be spherically symmetric, but not necessarily stationary. Again, this notion of redshift is observer independent. And it has played important roles (though sometimes manifesting in ways that are not immediately apparently related to red-shift, through choices of coordinates and what-not) in the study of dynamical, spherically symmetric gravitational collapse in the mathematical physics literature.
To summarise:
If you just compare the frequency of light measured (a) at its emission at the surface of the star in the rest frame associated to the collapse and (b) by an arbitrary free-falling observer, you can get basically any values you want. (Basically because the Doppler effect depends on the velocity of the observer, and you can change that to anything you like by choosing appropriate initial data for the free fall.)
One last comment about your last question:
You asked about what happens in the interior of the black hole. Again, any frequency can be realised by time-like observers locally. The question then boils down to whether you can construct such time-like observers to have come from free fall starting outside the black hole. By basic causality considerations, if you start with a time-like vector at a space-time event inside the black hole formed from gravitational collapse, going backwards along the time-like geodesic generated by the vector you will either hit the surface of your star, or exit the black hole. Though precisely how the two are divided depends on the precise nature of the gravitational collapse.
I should add that if you use the "global ruler" point of view, arguments have been put forth that analogous to how one expects red shift near the event horizon, one should also expect blue shifts near any Cauchy horizon that should exist. This has been demonstrated (mathematically) in the Reissner-Nordstrom (and similar) black holes. But as even the red-shift can sometimes run into problems (extreme charged black holes), one should not expect the statement about blue shifts near the Cauchy horizons to be true for all space-times.
Best Answer
If you're not up to speed with general relativity this is going to be hard to explain, but I'll give it a go. The more determined reader may want to look at this PDF (just under 1MB in size) that describes the collapse in a rigorous way.
A couple of points to make before we start: you're being vague about the distinction between the singularity and the event horizon. The singularity is the point at the centre of the black hole where the curvature becomes infinite. The event horizon is the spherical surface that marks the radial distance below which light cannot escape. As you'll see, these form at different times.
The other point is that to make the calculation possible at all we have to use a simplified model. Specifically we assume the collapsing body is homogeneous (actually I see you anticipated that in your answer) and is made up of dust. In general relativity the term dust has a specific meaning - it means matter that is non-interacting (apart from gravity) and has zero pressure. This is obviously very different from the plasma found in real stars.
With the above simplifications the collapse is described by the Oppenheimer-Snyder model, and it turns out that the size of the collapsing object is described by the same equation that describes the collapse of a closed universe. This equation is called the FLRW metric, and it gives a function called the scale factor, $a(t)$, that describes the size of the ball of dust. For a closed universe the scale factor looks something like:
(image from this PDF)
A closed universe starts with a Big Bang, expands to a maximum size then recollapses in a Big Crunch. It's the recollapse, i.e. the right hand side of the graph above, that describes the collapse of the ball of dust.
The radius of the ball is proportional to $a(t)$, so the radius falls in the same way as $a(t)$ does, and the singularity forms when $a(t) = 0$ i.e. when all the matter in the ball has collapsed to zero size.
As always in GR, we need to be very careful to define what we mean by time. In the graph above the time plotted on the horizontal axis is comoving or proper time. This is the time measured by an observer inside the ball and stationary with respect to the grains of dust around them. It is not the same as the time measured by an observer outside the ball, as we'll see in a bit.
Finally, we should note that the singularity forms at the same time for every comoving observer inside the ball of dust. This is because the ball shrinks in a homogeneous way so the density is the same everywhere inside the ball. The singularity forms when the density rises to infinity (i.e. the ball radius goes to zero), and this happens everywhere inside the ball at the same time.
OK, that describes the formation of the singularity, but what about the event horizon. To find the event horizon we look at the behaviour of outgoing light rays as a function of distance from the centre of the ball. The details are somewhat technical, but when we find a radius inside which the light can't escape that's the position of the event horizon. The details are described in the paper by Luciano Rezzolla that I linked above, and glossing over the gory details the result is:
This shows time on the vertical axis (Once again this is comoving/proper time as discussed above) and the radius of the ball of dust on the horizontal axis. So as time passes we move upwards on the graph and the radius decreases.
It's obviously harder for light to escape from the centre of the ball than from the surface, so the event horizon forms initially at the centre of the ball then it expands outwards and reaches the surface when the radius of the ball has decreased to:
$$ r = \frac{2GM}{c^2} $$
This distance is called the Schwarzschild radius and it's the event horizon radius for a stationary black hole of mass $M$. So at this moment the ball of dust now looks like a black hole and we can no longer see what's inside it.
However note that when the event horizon reaches the Schwarzschild radius the collapse hasn't finished and the singularity hasn't formed. It takes a bit longer for the ball to finish contracting and the singularity to form. The singularity only forms when the red line meets the vertical axis.
Finally, one last note on time.
Throughtout all the above the time I've used is proper time, $\tau$, but you and I watching the collapse from outside measure Schwarzschild coordinate time, $t$, and the two are not the same. In particular our time $t$ goes to infinity as the ball radius approaches the Schwarzschild radius $r = 2GM/c^2$. For us the part of the diagram above this point simply doesn't exist because it lies at times greater than infinity. So we never actually see the event horizon form. I won't go into this any further here because it's been discussed to death in previous questions on this site. However you might be interested to note this is one of the reasons for Stephen Hawking's claim that event horizons never form.