Consider the red wines of Nauosa in Makedonia. They are made with a grape called Xinomavro (translates as acid and black), sometimes compared to Nebbiolo and Pinot Noir. Top Nauosa producers include Ktima Kir Yanni (I reccomend the Ramnista bottling), Karydas, and Boutari. If you want something a little less rustic Ktima Kir Yanni makes a non appelation blend of Xinomavro and Merlot called Yianakohori which is excellent.
BTW redwine and redsox, Retsina is not a varietal , but rather an Appelation of Tradition, where a fairly acidic blend of Savatiano, Roditis, and other varietals are flavored with pine resin.
If you want to get into the greek wine thing try http://www.greekwinemakers.com.