Marrakech is where most tourists seemed to go, but I personally liked Fez. It was once the capital of Morocco and the intellectual capital of the world.
Compared to Marrakech, it seemed to have a more 'authentic' feel...which just means it wasn't very touristy. A trip through the souk in the medina is an adventure within itself. Order yourself a delicious serving of pastilla and some tajine and sit down and take it all in.
Speaking of which, you could just catch a flight to Rabat-Sale, and check out the King's tomb and the Phonecian necropolis Chellah. Or you could stay close to the medina and go check out the Atlantic Ocean by way of the Oudaya. If you're feeling like you want to see more of the country, then from Rabat, you can catch the train south to visit Casablanca, Marrakech and Agadir. Or, you could go north of there and check out Fez or Tangier (which is where you can cross over to the Spanish territory of Ceuta while remaining in continental Africa).
On the way, you could stop off in Meknes (a smaller city) and check out Moulay Idriss, a town that sits up in the mountains. You can catch a cab up there with some other travelers to split the far and you might even catch a glimpse of a shepherd tending to his flock on the road up to the town
Be sure to brush up on your French before going, though Spanish will help you more up in the northern part; Darija would cover you much better all over though.
