Hmm, I had trouble playing as Lithuania, myself. It just seemed like I couldn't get enough money together. Plus the fact that you've got enemies on all sides, and you're 'royal' unit is Lithuanian cavalry early on. The only thing I like about them is their color and the way their troops look. As for Volga Bulgar, well, I've never been dumb enough to try them on high period.

Also, who ever said Poland was easy? I've found them to be quite difficult, myself. Stuff just always seems to go wrong for them.