What about Greece? Lots of history, lots of stuff to do, and it's cheapcheapcheap once you get there right now.
Morocco is also incredible. Fascinating history, some culture shock, and just really different than the places she's already been. Turkey might be good for this also but I haven't been so I can't say for sure.