You want it to display the instant they click the "Submit" button? The issue here is that, even if the "Loading..." popped up, the user would immediately see the page go white as the new page begins to load. It seems you're wanting to combat how page refreshes work, not Drupal.
That being said, to achieve the functionality that I think you're looking for you'd want to be opening the node create/edit form in a modal or something like that so it submits via an Ajax call and not a standard HTTP refresh. You can maybe use the Popups API module to do something like this: http://drupal.org/project/popups