I was at a place that needed to have this done. We didn't have consistent results when we tried producing a "please wait" page itself. What we found worked really well was a pop up window which was just an HTML page in a new window. This window would say something like "Loading. Please wait..." and we put an animated GIF in it (oh yeah - we wanted the animated GIF to run but when a new page has been requested, IE stops running animated GIFs so thats why we did the pop up window).
We launched the pop up window when the user hit submit. And then on the results page we called a function to close the window in the "onLoad=" in the body tag.
If the user didn't have JavaScript, it wasn't a big deal and the page did load.
I have seen this done with DHTML - and I might have done it back in the day. For the DHTML to work, the user will definitely need JavaScript enabled and working around that became tough. But it is an option.