As stated above, preloaders or loaders that let the user know what is going on are the way to go. Sometimes an "attract loop" will work as well, but that is more for idle times or kiosks.
An application is a dialogue with a person, so strange pauses where the user may be confused or left waiting without knowing what's going on is going to create a suboptimal experience for the user. This is evolving every day, the more times goes by, the more needy the user will become.
Think of your user like a really needy girlfriend. She always needs to know what's going on. She always needs reassurance and attention. Otherwise she'll find it somewhere else... there are a lot of apps in the sea.
One thing I can add to this is to make sure you are really thoughtful about the way you are breaking up your content and loading. Don't preload a whole site unless you have a good reason to. But at the same time, don't make every little move load something, it'll make for a choppy experience. I'm always leaning toward the side of only loading what the user wants when the user wants it, making the experience a lot more snappy, taking from the Ajax sort of paradigm.
Oh, and as for what the preloader should be... You should really set your standards high. Perhaps it could be something informational that enhances the usability of your site, or the current user's flow. Maybe it's a really catchy logo that further engrains the brand in the user's mind. Maybe it's humorous, or and impressive animation that somehow flows well with the content the user is waiting for. Just because it's a preloader doesn't mean it should be boring or overly informational, like a 59% ------> sort of thing.