Since the additions necessary to make it support Polish are relatively modest (although the ogonek is tricky to pull off nicely) you might consider commissioning a customization of Oleo. Of course that's assuming you don't find something close enough in style that does support Polish (unless you happen to want something nobody else has - a big bonus in terms of branding). If you do want to look into such customization there are many people on Typophile (including yours truly*) who could do a nice job of it.

* hpapazian at gmail dot com

As for a good text companion, you might consider Adelle Serif.

hhp