Oooh, Krakow
I love that place, spent a week there with my family a couple of years back. If you have a chance, visit the Wawel Castle for some fine architecture and a Renaissance feel. Kazimierz, the old Jewish district, is also worth a walk. And if you have some leeway in your travel plans, visit the Wieliczka salt mines in the Tatra Mountains, about 60 mi. from Krakow. A lot of the hotels organize tours there, and I promise you won't regret it. The huge underground Catholic chapel made entirely out of mineral salt is definitely worth a visit.
Just as long you don't lick the life-size statue of John Paul II. The locals don't like that.
And if there's a special someone... Poland is known for beautiful amber jewelry. Take a look; me, I got me an amber rosary for my clerical roles at the Medieval Market.