I thought it might be useful to collect any useful information I encounter while studying languages, both for myself and any other learners out there. I know I always spend quite a bit of time trying to find good books and materials when I first start a new language, so I hope this is helpful!
In general, a good way to start is to get the Assimil book/course for the language and supplement it with one or two other books, while using Anki (or a different SRScache) to study and retain vocabulary (and possibly grammar) encountered in those books. Here's a review of Assimil if you don't know about it yet.
I will focus on the languages that I actually intend to study, but I'll gladly add others if you have recommendations. The way I chose my languages is pretty straightforward, I simply picked the most popular onescache, with a slight bias to European languages - I live in Europe, so those will be more useful to me.
The order below does not reflect popularity, but rather my order for learning.
My native tongue, not much to choose there. I'm glad I don't have to learn it, genders for nouns are rather arbitrary and grammar is quite complex. Feel free to message me if you have any questions about the language. While I don't know any learning materials I can vet them for correctness if you send me a pdf.
Learned it from around ten years on, mostly by massive exposure to books and movies, as well as writing a lot on the Internet. I did have English classes in school, but measured by the performance of my classmates those were rather ineffective.
Note that I actually never visited an English speaking country until I was already fluent, and at least grammatically better than the average native - I scored 2350 on the SAT, with only losing points on the essay. I therefore believe that while exposure to natives is helpful for learning a language, it's not actually necessary. Consuming media in your target language can provide much of the same benefit, even provide you with a larger vocabulary than your average native speaker is going to use during the course of his day. So if you have the chance to study abroad by any means take it, but don't feel discouraged if you don't.
There's a fairly interesting test for your vocabulary size - I very reliably got 80%.
I studied Spanish for the last three years of my high school, completely stopped using it for close to two years, then started practicing again about a year ago. I'm nowhere near as proficient as in English, but I can follow TV shows and podcasts as long as they use clear pronunciation. Very casual conversation and South American accents are still difficult, though I hope to improve.
This is the first language of this list that I'm still actively studying, so I can actually make some recommendations. At the moment, I try to listen to at least half an hour of podcasts every day. My absolute favorite is Radio Ambulante. Otherwise just listen to whatever you'd listen to normally, but in Spanish. Audio-books also tend to work great.
Japanese I started much more recently, sometime during April of 2013, so I have a lot more experience with starting from scratch. My initial attempts were not very efficient - and I almost didn't study at all while traveling for July-September -, but since then I've found some very good materials.
For studying Kanji, that's definitely WaniKani. For grammar, things are more diverse. There's Tae Kim's Guide to Learning Japanese and IMABI, both free. Then there's more traditional textbooks like Genki. Additionally I strongly recommend Assimil, primarily for the recordings.
If you want to learn Kanji while making your own flashcards, Kanji Damagecache is a good source for mnemonics and readings - similar to WaniKani, but free. Or if you like the content of WaniKani, but dislike the interface, you can export to Anki using wanikanitoankicache (this is how I currently use it). There's also an Anki deck for writing practicecache.
Once you already know a few hundred Kanji, Read the Kanji is a great website to keep practicing them while reading actual Japanese sentences. There's also a new site coming up, Satori Readercache, that has a really awesome interface. Satori Reader is currently my favored way to practice reading.
The books above are great for looking up grammar, but for actually learning it you'll want to write short example sentences and put them into Anki, as described in Fluent Forever. For very specific questions remember there are also Wikipedia articles on grammarcache and verbscache, as well as a verb revision sheetcache.
For more reading practice, either get some of your favorite Manga (I have Attack on Titan, Death Note and Naruto) or check out チョコチョコ大図書館cache and Duendecatcache. For listening there's Erin's Challengecache and My Kikitoricache. A much more advanced version is listening to TED talkscache.
I've started Russian much more recently, January 2014, with the first months spent just trying to figure out good resources to learn from. I finally settled on Assimil, augmented with The New Penguin Russian Course. The former for it's excellent listening exercises (I feel it's essential to learn words and phrases with correct pronunciation and emphasis), the latter because it provides more in depth grammar explanations and a lot of vocabulary lists.
Making your own vocabulary lists and adding them to Anki is a lot of work. Luckily, you'll often find that other's have already done it for us. In this case, patou454 has added all words for the Assimil book to a very comprehensive Memrise course. The first 30 levels even include audio! There's also another one for the New Penguin book, though that one has to be used in conjunction with a more general Beginner's Russian course. That's not too much of a problem though, Memrise has a handy "Auto-Ignore" feature so you don't have to study words multiple times if you do more than one course. It's under "Learning Options" on the level overview.
Aside from the characters (which are easier for me due to Japanese), Chinese has an additional difficulty: tones. The difference between mā (mother) and mǎ (horse) is just the direction of your voice (flat vs fall-rise). But wait, there's more. In addition to tones, Chinese has consonants that are quite hard to distinguish for us: jī vs qī or xuān vs shuān.
The best way I've found to deal with this so far is Chinese Pinyin Trainercache, a cheap Android app that quizzes you on minimal pairs that only differ in tone or consonant. Once they are out, Gabriel Wyner's Pronunciation Trainerscache might also help.
In total, I want to become fluent in roughly 10 languages. Apart from the 7 above, that's 3 more languages, listed below. The order is still sketchy, since I haven't actually started any of these languages, and might change if I actually need one of those languages for a specific reason.
Italki gives you easy access to (cheap) professional tutoring. I haven't actually used it myself (yet), but it looks very promising.
Below a map of the countries where I'm already able to communicate in the native language: