I also recommend Genki very much! It gives you a very good foundation of both grammar and vocabulary, and I found that after Genki I and half of Genki II I could without trouble start learning Japanese from just reading and watching things in Japanese and looking up words. Moreover, if you are really motivated you can get Genki I done in just a couple of weeks because it has very easy grammar explanations and such.
For beginners I really recommend learning from games and manga, especially shoujo manga because it is generally more dialogue-based and often has furigana over the kanji. My first manga in Japanese was Hana Yori Dango, and it is incredibly easy! For games I think the Ace Attorney series is great because it is text-based, and as long as you learn words like 'murder-weapon', 'evidence' and 'trial' it is easy to understand. Even though some things might look discouragingly difficult at first, if you understand at least the main plot, or more generally understand the story, it is a good level (or at least that is my motto).
Dramas and variety shows are good too(without English subtitles!). In variety shows people sometimes talk fast, but they usually partly put subtitles when people speak, which is useful if you have trouble hearing. My favorite are しゃべくり007, 笑っていいとも, and ダウンタウントーク.
I also recently found a very good youtube channel that explains grammar and vocabulary in Japanese!
https://www.youtube.com/user/freejapaneselessons3