Right sorry about that. I posted this quite late into the night and I wasn't all too lucid.
No worries, I replied early morning before I found my glasses or drank a coffee ;-)
Roger's suggestion of Sękacz is a good one. Most food shops in town should have it (and definitely not a whole one!). Cherries in chocolate and alcohol are good too, as is nalewka, Wiśniówka is a nice one. Tins of goose pate are good (get from Krakowskie Kredens or whatever it's called, at Nowy Swiat 23 rather than the supermarket; they have lots of traditional stuff in fancy boxes which make nice gifts).
A good bottle of vodka always goes down well. Contrary to what people say, there isn't that much difference between them, if you exclude the bottom and top 10% of the price range, so just choose the one with a label that looks good.