Display a message during form submission and prevent multiple submissions
This can be achieved by creating an AJAX form. If you fear that the max execution time of the server will be a problem you should look into batch operations as mentioned by Kevin. 

An easier alternative is to add a custom JavaScript file and react on the form submission.

Alter the forms you want to behave as requested in a custom module. Use the #attached property to add your custom JavaScript file (in your custom module directory).

$form['#attached']['js'][] = drupal_get_path('module', 'MODULE_NAME') . '/MODULE_NAME.js';


Then add something like the following to your JavaScript file:

(function ($) {
  Drupal.behaviors.formSubmitFeedback = {
    attach: function (context) {
      // Get the forms we want to modify by form ID.
      var $forms = $('#form_id_x, #form_id_y'),
        submitCount = 0;

      // Make sure the form is only submitted once.
      $forms.once('submit-feedback').submit(function(e) {
        if (submitCount) {
          e.preventDefault();
        }
        else {
          var $submits = $forms.find('input[type=submit]');
          // Hide all submit buttons so that they can't be clicked twice.
          $submits.hide();
          // Add a class to the form so we can do some specific styling.
          $forms.addClass('submit-wait');
          // Add a wait message with throbber after the submit buttons.
          $submits.after('&lt;p class="submit-wait-txt ajax-progress-throbber"&gt;&lt;span class="throbber"&gt;&lt;/span&gt;' + Drupal.t('YOUR MESSAGE') + '&lt;/p&gt;');
          // Make all input fields (except the submit buttons) readonly.
          $forms.find('input').not($submits).blur().prop('readonly', true);
        }
        submitCount++
      });
    }
  };

})(jQuery);


This piece of code hides the submit button and cancels later submits.
A message is added to the DOM with a Drupal throbber (depending on your theme). You may need some CSS to make it look nice. There will be a 'submit-wait' class on the form after submission.