BENNCOOL,
If you are mainly interested in wrecks, the northern Red Sea is the best with Hurghada as your starting point. There are several one week "wreck"-safaris. If you are prepard to travel as far as Australia you might want to consider Truk lagoon in Micronesia, wich is where a WWII battle took place between japaneese and american fleet forces. Not a wreckie myself, but I confess that I know several people who are, and they rank Truk as really good. Also Scapa Flow in Scotland and Narvik in Norway has very good wreck diving without all the girlish corals and pretty fishes ... Haven't stayed on the Lady M, but I gave been onboard her and know several people who have used here. It is a medium to high quality boat.
TEERLKAY, Elphinestone can be the greatest dive in the world, but you will need the right conditions. The north point is my favourite dive here, where I have seen schooling hammerheads several times, silvertips on a few occations and grey reef sharks on almost every dive. I have also seen an oceanic whitetip on Elphinestone once, but not on the north point. If you are an experienced diver, comfortable with deep diving, you can also ask your dive guide about doing the Arch under the south plateau - a dive which is really not reccomendable due to the risks - but it's there and it has a fascinating story attached to it. It is said to hold an ancient sarkofag of an old egyptian pharaon. Not very believeable, but anyway ...
good luck
