Zamość is a must-see.
I'd have to second that. Zamosc should be required viewing for all visitors to Poland. I'm always amazed at how few tourists there are in the place.
Sandomierz is also well worth a visit, but perhaps not at the weekend.
In the same sort of area as Zamosc is a nice little place called Zwierzyniec with a wonderful brewery and a nice park with a church in the middle of a lake. And you need to stop in Szczebrzeszyn (it's on the road from Zamosc to Zwierzyniec).
Przemysl is worth a visit too, as is Sanok.