El Djem in Tunisia - in much better shape than the Colisseum in Rome and you could go everywhere in it and get a real understanding of what the ancient Roman Gladiator events were like.
Al Deir at Petra - most people ooh and ahh over the Treasury, but if you take the time to make the long hike to Al Deir, you will get a fantastic view across a canyon to an amazing building carved completely out of stone, more magnificent than the Treasury in my opinion.