What I suggest is Marsa Shagra (Egypt) or one of the resorts in the area around Marsa Alam. Shagra is one of my favorite places in the world to dive. It's all about diving (literally nothing else to do there). The house reef starts just under the surface and you can make nice shallow, long and interesting dives both day and night with lots to see and very little hindrance from tidal flows. Water temperatures vary from very warm in the summer to about 23-24C in the winter. Visibility is usually in the 20-40 metre range and the weather top-side is usually very good.
There are also daily guided dives (going with the zodiac or with a truck) with possibilities to see, among other things (no guarantees), large sea turtles, a manatee, large sting rays, guitar sharks/rays, dolphins, small octopus, small reef sharks, large eels and at least one easily accessible wreck dive suitable for beginners. Some of the animals (eels, octopus and several other species) are nocturnal so you won't see them during the day except in exceptional circumstances. To see large sharks requires diving an offshore reef that really isn't suitable for beginners in terms of depth and current.
Moreover, the location is perfect for doing your AOW (include night, deep, navigation, nitrox and naturalist) and there are instructors on site who teach well and can teach you in fluent English. The operator is called Red Sea Diving Safaris
R..