I used to study Spanish but have become quite rusty at it due to lack of use over the last 10 years. Quite interested in picking up either German or Russian (I like both, I just haven't settled on one yet).
As a native Russian speaker, may I advise German. Russian has all the grammatical complexity of German + non-Roman phonetics + Cyrillic alphabet + word order that's not prescribed, but has stylistic meaning.