I took my group on the VIP One liveaboard (
www.vipone.com), which was launched in 1996, but is drydocked every year, so it is in very good condition. The interior was recently totally redone. I like this boat because it is a decent size, yet it only takes 14 guests - most boats that big take 20. So you have plenty of room, dive sites aren't crowded when it is just your boat, the crew are great and the food is excellent.
There are several other boats operating out of Sharm running similar itineraries, but I have been on this one, liked it, and am planning on going again in 2007 (time allowing).
If you are doing the northern itinerary, as was said before, June is the time to go, as this is when Ras Mohammed is at the height of its powers. Massive and I mean massive shoals of unicornfish, snapper, batfish and jacks hanging off the sheer wall, giant trevally and grouper swimming in and around them, and slightly further off the wall, in the blue, hundreds and hundreds of barracuda swimming in a large circle, generally with two or three blacktip sharks worrying them. Oh, and then there is the stunning coral growth to look at if you can tear yourself away from all the open-water action.
Mark