Change javascript to fade in over the top of each other instead of fadein/fadeout?

Question 1

I think some of these other solutions are over thinking it. You were already so close. Instead of fading in and out the one image, you need to fade in a new image over top each time. I tweeked your code slightly below.

Here is the jsFiddle: http://jsfiddle.net/Q5YYG/

$(document).ready(function () {

    var $backgroundimages = ['http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/home-test.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/qanda-front.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/home-page-slide.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/TCE-New.jpg'];
    var $backgroundcount = 0;

    function fade($ele) {

        // Determine which image is next
        $backgroundcount++;
        if ($backgroundcount >= $backgroundimages.length) {
            $backgroundcount = 0;
        };

        // Put a new hidden image in front of the original image
        var $new_element = $ele.clone();
        $ele.after($new_element);
        $new_element.hide().css('background-image', 'url('+$backgroundimages[$backgroundcount]+')');

        // Fade the new image in
        $new_element.delay(5000).fadeIn(1000, function() {

            // After the new image is visible, remove the old image.
            $ele.remove();

            // Do the same thing over again
            fade($new_element);
        });
    };

   fade($('#stretchParent .HomeImage').first());
});

Question 2

It would be easiest to create an element for each image and then fade the elements while manipulating the z-index at the same time.

SEE THE EXAMPLE HERE

Since you're already using jQuery, just use .each() to iterate through the array and append the elements to the container element, #stretchParent.

$.each(backgroundImages, function (index, value) {
    $('#stretchParent').append('<div class="HomeImage" style="background-image:url(' + value + ');"></div>');
});

As for the function itself, i'd suggest using setInterval. Set the delay to whatever you want.

setInterval(function () {
    el = $('#stretchParent .HomeImage');
    el.first().css('z-index', 2).fadeOut(1000).appendTo($('#stretchParent'));
    el.eq(1).show().css('z-index', 1);
}, 3000);

The function increases the z-index of the first element and then fades it out and appends it to the end of the container element. The next line simply makes the next element visible while decreasing its z-index to ensure that it will appear behind the current image.

EXAMPLE HERE // FULL SCREEN EXAMPLE HERE

Question 3

Why not http://jsfiddle.net/tX7Cp/:

fading to opacity of 0 or 0.2 (something low to give a more overlapping effect)
changing/cycling the background image
fading to opacity of 1
setTimeout call of the fade function in 5 seconds

You can call the first entry call on a timeout if you want to initially display the first image for 5 seconds.

Additional important note, you might want to preload the images so that the first time cycling around the retrieval of the images from the server doesn't interfere with the smooth fades. Perhaps cycle once through requesting the images before you start, or alternatively having dummy tags loading the images off screen.

var $backgroundimages = ['http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/home-test.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/qanda-front.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/home-page-slide.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/TCE-New.jpg'];
var $backgroundcount = 0;

function fade($ele) {
    $ele.fadeTo(1000, 0, function(){
        $ele.css('background-image', 'url('+$backgroundimages[$backgroundcount]+')');
        $backgroundcount++;
    }).fadeTo(1000, 1.0, function () {
        if ($backgroundcount >= $backgroundimages.length) {
            $backgroundcount = 0;
        };
        setTimeout(function(){
            fade($ele);
        }, 5000);
    });
};

fade($('#stretchParent  .HomeImage').first());

Ideal Solution

Here's a overlap fading solution with alternating images:

FIDDLE

<div id="stretchParent">
  <div class="HomeImage" style="background-image: url(http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/home-test.jpg);">
  </div>
  <div class="HomeImage" style="background-image: url(http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/qanda-front.jpg);z-index: -1">
  </div>
</div>

var $backgroundimages = ['http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/home-test.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/qanda-front.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/home-page-slide.jpg', 'http://www.universitycompare.com/wp-content/themes/blue-and-grey/images/TCE-New.jpg'];
var $backgroundcount = 1;
var $elems = $('#stretchParent .HomeImage');

function fade($ele) {
  $other = $elems.eq($backgroundcount%2);
  $other.css('opacity', 1);
  $backgroundcount++;
  $ele.fadeTo(1000, 0, function(){
    $other.css('z-index', 0);
    $ele.css({
      'z-index': -1, 
      'background-image': 'url('+$backgroundimages[$backgroundcount%$backgroundimages.length]+')'
     });

   })
   setTimeout(function(){
     fade($other);
   }, 5000);
};

fade($elems.first());

Question 4

First of all let me point out that you will require two or more overlapping elements to get such a thing working. I am not going to write the code for you, but I would suggest creating a single <img> element for every background image and positioning that stack of images directly behind the element in question. In case you do not care much for making it yourself you can check this css3 solution (demo 5 and 6) or this jquery plugin.