To answer the OP.
I studied a lot of languages at school but also in general as I enjoy them. Coming from a somewhat mixed heritage I have from an early age been exposed to a lot of languages - this does make it easier.
However, despite studying Spanish at school, after spending extended periods of time there (in Spain) it really did improve my Spanish dramatically, and actually having the guts to try it.
Lessons are also great - but I find interactive lessons with someone to be more useful just because you can stop and ask questions.
Grammar is the key to a language - once you learn the basics, you can add the vocab around it. Even if you just learn the basic tenses of verbs (past, present, future) without worrying initially about the continuous and perfect and conditional tenses to name a few. Though in French certainly there are many many different versions of the past/present/future, which subtly but importantly change the meanings. That said you can get by in general to make yourself understood with basic tenses.
I also learned to speak a little Greek (being part Cypriot as well) and whilst I can understand and read it, I never took the time to learn the grammar, so my Greek is very pigeon Greek and just a string of nouns and adjectives together rather than well constructed sentences.
I also studied Arabic a little later in life (mid to late teens) as I spent a lot of time in the Middle East I also had an option to study it at school instead of General Studies. Completely different construct (no verb "to be" for example) and massively different alphabet and just really alien. However, with a bit of structure, and if you have a good understanding of grammar, it's easy enough to pick up. My Arabic is now poor owing to lack of practice (though I had a small conversation when in Dubai, which surprised me!), but I know enough to break the ice and muster a little bit of respect and broker than initial relationship which is important.
Immersion is key along with structured lessons. I've never tried those self study tapes so I cannot comment on how good they are.
For example I'm teaching myself object oriented programming at the moment, and I'm self learning, it's hard, because I can't ask the stupid questions to real people and have to scour the net to find the answers and even then I'm making assumptions. So at some point I will have to cough up and take lessons if I want to become more proficient at it. That's just how I learn, some people can do it more viscerally, I need something more structured to understand the basic constructs then I can add to that quite quickly.
It's hard, but you can do it, you will just need to put the effort in. Good luck!