Greece - I’ve been to Athens, Thessaloniki and the Chalkidiki Peninsulas. I’ll skip Athens because you lived there. Macedonia was one of the highlights of my travels. Keep in mind that when I travel, I travel as a boheme, not a tourist. I tend to blend in with the locals and immerse myself in their customs and ways. I do take the time to see tourist sights (like the acropolis) if they are significant to the culture (I avoided Euro Disney while in France). If you travel differently, ignore my recommendations.
Thessaloniki is a great city - They adore Alexander the Great and some locals, upon finding out I was American, treated my to a whole day of history lessons. They took me to the White Tower and their proud (and wonderful) Macedonian museum where the bones of Philip are displayed along with weapons and fabulous treasures of Alexander and his vast empire.
I took a bus out to the gorgeous Kassandra Peninsula and spent two days doing nothing but lounging on the beach, swimming and partying with the greeks. Highly recommended. One of the other peninsulas, Athos, has a 1000 year old monastary which I wanted to visit, but I found myself having too much fun on the beaches.
I spent five days in Istanbul sharing a local room with two women from Germany I met at the train station. They were very familiar with the city and showed me everything. I loved the Blue Mosque during prayer (partake of some turkish hash, go into the Blue Mosque, take your shoes off, and let yourself slip away - I was in there for hours, travelling into the past) and Aya Sofia (what a history that building has had!) and you’ve got to go to the covered bazaar. Be very watchful of scams, I was approached many times by slimey men offering me some tea (delicious) or other enticement only to be find out they were salesmen trying to trap me into buying something (usually leather jackets).
Also visit the Topkapi museum to see the hair & footprint of Mohammad and watch the endless prayer.
I spent a lot of time on the Bosphorus, on boats or in outdoor cafes talking to the locals and playing music - I met some great people. Blend in and get lost. Also make sure you go over to the asian side of the city at night (go to someplace high) and look back over the straits at the lights of the sprawled city - beautiful.
I haven’t been to Egypt, but I hear the terrorists are really nice and will take your picture for you. Also, camels are pretty nasty creatures.