Should I learn Russian or start Polish when it arrives ? I'm very interested in both cultures but I'm not sure which of the two to pick.
Russian has the advantages of being a bigger language: more resources, more media, lots of professional opportunities. Polish is a language of a rising nation within the EU in business and politics, a much more nearby destination for the europeans, with quite a lot of resources and media, considering it is smaller
Russian is understood in the eastern europe (not central, it can as well be viewed as offensive due to the 20th century history), in central asia too. And among the russians elsewhere of course. Polish is a language of only one country and the poles abroad. Russian gives you some intelligibility with Ukrainian and Belarussian. Polish shares a lot with Czech and Slovak. Russian might impress more employers on your cv but Polish gives you access to a smaller niche. So, it is a question of your strategy :-)
I'd say there isn't much of a difference in difficulty of grammar or pronunciation, both are likely to be harder for you than French or Catalan. Russian might have more French loanwords, Polish the German ones, for historical reasons. Don't let cyrillics drive you away from Russian, it can be learnt in one afternoon, it is not a problem, other things are ;-)
So, I'd recommend you to listen to both, have a look at their music bands, writers (whether you are lover of the classics or the fantasy/scifi, both Russian and Polish are awesome!), etc. Perhaps you've already got friends speaking one or the other. And choose whichever you personally prefer. I wouldn't recommend you to learn both at once with the attitude "oh, it's the same anyways, who cares". Each of them can be a challenge and they are quite distinct. But should you learn one and want the other, it should come a bit easier.
I recommend this overview of the slavic (and baltic) languages: http://how-to-learn-any-language.com/forum/forum_posts.asp?TID=26165&PN=1
I meant Latin in particular. :-) There are many similarities in grammar. As Latin has proven awesome for learning the romance languages in terms of vocabulary (and to much lesser extent the grammar, I'd say), it has been quite helpful for my German studies and I saw so many similar features with my native Czech (which is quite similar to Polish). So, Latin is actually much more of help than many people expect.