Dear Renato, The first thing I would do is get a good idea of the history and geography of Eastern Europe from an encyclopedia such as Wikipedia, because the history of Galicia in the era you need is very confusing.Then I would search the Hamburg Passenger Lists on Ancestry to find your grandfather.Some huge percentage of Eastern Europeans traveled to the Americas through Hamburg.I think it was as high as 90% of them.
Here is a brief history.
Poland The establishment of a Polish state is often identified with the adoption of Christianity by its ruler Mieszko I in 966, over the territory similar to that of present-day Poland. The Kingdom of Poland was formed in 1025, and in 1569 it cemented a long association with the Grand Duchy of Lithuania by signing the Union of Lublin, forming the Polish–Lithuanian Commonwealth. The Commonwealth ceased to exist in 1795 as the Polish lands were partitioned among the Kingdom of Prussia, the Russian Empire, and Austria. Poland regained its independence as the Second Polish Republic in 1918.
Partitions of Poland by the Congress of Vienna Participants
The First Partition of Poland, which the Poles proved incapable of resisting, was decided on August 5, 1772. Two decades later, Russian and Prussian troops entered Poland again and the Second Partition was signed on January 23, 1793. Austria did not participate in the Second Partition. The Third Partition of Poland took place on October 24, 1795, as soon as the Polish Koœciuszko Uprising was defeated. With this partition, the independent Polish state ceased to exist.
Galicia The nucleus of Galicia lies within the modern regions of western Ukraine: Lviv, Ternopil and Ivano-Frankivsk near modern Ukrainian city of Halych.
The territory was settled by the East Slavs in the early middle ages and, in the 12th century, a Rurikid Principality of Halych (Halicz, Halics, Galich, Galic) formed there, merged in the end of the century with the neighboring Volhynia into the Principality of Halych Volhynia that existed for a century and a half. By 1352, when the principality was partitioned between the Polish Kingdom and the Grand Duchy of Lithuania, most of Galicia belonged to the Polish Crown, where it still remained after the 1569 union between Poland and Lithuania. Upon the partition of the Polish-Lithuanian Commonwealth in 1772 the Kingdom of Galicia and Lodomeria, or simply Galicia, became the largest, most populous, and northernmost province of the Austrian Empire, where it remained until the dissolution of Austria-Hungary at the end of World War I in 1918.
So it looks like you should look for Galicia in Austria for the time period that your grandfather came.