Not counting the Ottomans, you've got Poland-Lithuania, the Hapsburg Empire of Austria, and Russia. Russia is unlikely--they had a vast frontier to colonize on their own border and no viable port from which to launch colonization fleets. Poland-Lithuania also had a frontier and an unfriendly neighbor who controlled the only way out of the Baltic. Hapsburg Austria had a direct money-line to the Spanish colonies, so they've no reason. The Ottomans had no reason to try overseas colonization (they had the Mediterranean and a good amount of the continental Asian trade).
So, of the Eastern European states, Poland-Lithuania is the best bet, and it's not a very good one. One would have to either make the PLC friendly with both Sweden and Denmark (the latter for actually controlling the straits, the former because its Navy was the real power), or neutralize Sweden.
I can see a joint Polish-Lithuanian-Muscovite struggle in Livonia and Finland against the Swedes, cutting them off from the Amber Trade, and maybe one can start a religious war in Sweden between the Lutherans and Catholics, if one can prevent the immediate royal conversion to Lutheranism there and begin a dynastic struggle between a Catholic and Lutheran Vasa branch unconnected to the Polish branch (imagine, spreading the 30 Years War into Scandinavia). Sweden torn up, the PLC becomes the de facto leader of the remaining trading powers in the Baltic (until Russia builds her port). She constructs a fleet to keep the Germans in line, and broadens her horizons to include a fur-extraction colony in Canada as a way of undercutting the Russians' domination of that market.
But in order for the PLC and the Muscovites to ally together, they may have to work out on some sort of a rapproachment, which might mean preventing the Times of Troubles from ever occuring. At the most, Poland-Lithuania might even have to dominate Brandenburg-Prussia if they want some leverage for gaining colonies. Perhaps the PLC expands into the Balkans in order to get access to the Mediterrenean Sea and possibly colonize parts of Africa. I admit that in this case, India could either be ruled by Prussia, Poland-Lithuania, or even China.
So realistically, the only way Poland-Lithuania can realistically get colonies elsewhere would be if Sweden is screwed. So maybe Poland-Lithuania and Russia could become the Eastern European counterparts to Spain and Portugal in terms of exploration and colonization.
I was thinking before the Time of Troubles. Ivan IV of Russia had many admirers among the Polish gentry (not the Lithuanians, though), and there was talk of electing either him or his son King of Poland. They also jointly warred against the Swedes in Livonia in those days. If one can resolve the Ukrainian Issue in a manner satisfactory to each of the four major parties (Poland, Lithuania, the Cossacks, and Moscow), then this relatively good relationship can continue.
As for the Balkans, it seems that the Slavic peoples under Ottoman rule in the Danube basin viewed the PLC as a possible liberator under the reign of Stefan Bathory. Polish adventures that deep into the Balkans, however, were short-lived.
A Hungary that also joins the PL-Muscovite Commonwealth could also provide some heavy duty back up against both the Ottomans and the Swedes. There was also a plan to include Hungary in the Polish-Lithuanian Commonwealth as well. Oh, and the Teutonic Order has long been destroyed at this point, unless you count Ducal Prussia as one of the Teutonic successors, or even Brandenburg for that matter.
what about Prussia ? if they never gained western german land after Vienna. they will be considered eastern european nation. They have more resources than Courland, although still blocked by Denmark.