Well, we spent a week on the MV Tala (Red Sea Explorers) in October of 2009. It was a FABULOUS trip! The boat was comfortable, with fairly large cabins with private baths, and AC. The salon had a wide screen TV to review photos and videos, and also to get the wonderful 3D dive briefings. The crew was delightful -- very good company and very good in the water. You could do whatever sort of dive you wanted -- guided or not, shallow or deep, and as long as your gas supply allowed. I simply can't say enough good things about the folks on the Tala -- they know how to help you extract every last drop of fun possible from every diving day.
We did the northern itinerary, with some of the wrecks (like the Thistlegorm, which is the best wreck dive I've ever done) and then went over to the Brothers Islands, which are fantastic reefs and where I saw my first hammerhead sharks, as well as sea fans the size of Volkswagens.
I wish I could go back. The boat wasn't expensive -- it was getting to Egypt that was the project!