First thing I would recommend is the Holy Trinity chapel in the Lublin castle.
( For now
) You can visit online under the link below : http://www.vtour.pl/wirtualny-spacer/3060/lublin/kaplica-trojcy-swietej-w-lublinie.html
I know that it is not the church. However the chapel is quite important. Founded by Polish king - Władysław Jagiełło decorated fully by eastern iconography! (1418 A.D.)
Secondly I would recommend The Orthodox Church of the Transfiguration of the Lord - close to the castle. I used to attend the divine liturgy there. You can't miss it.
Worth seeing is also The Greek-Catholic Church of the Nativity of our most holy Virgin Mary. Beautiful, historic and wooden church. Now it is a part of bigger museum complex (but I think there is still service) .
That's just for now. I need to think about Kraków and Białystok. There is a lot to see.
But how much time do you have for each city?