Take a look at travel sites and see how they do it. Personally, I prefer Kayak's approach: show whatever you do have as soon as it comes in.
In this case, it sounds best to display some real progress dialog. Some people suggested 'reticulating splines' messages, which were very popular in Will Wright / Maxis games. I guess the trick here is finding appropriate messages to display and associating them with tasks/events in your load sequence that are long enough to be meaningful, but short enough that the user doesn't feel it dragging.