Just sarting so in the same situation myself.
I've gone for Genki as the best I've seen so far. Plus the work book, and will get the Kana/Kanji one next.
Also grabbed Barrons mini Japanese Grammar book, and Gilhoolys 'read and write Japanese scripts' which is a nice introduction to Kana and Kanji.
But am far from impressed by what I've seen of the choices so far.
But then I'm generally underwhelmed by language tuition books in general, and I've seen some stinkers in my time (Yes, I'm looking at you Cambridge Latin...).
But I'm a hard one to please though as I know what I want, just can't find it for Japanese yet (Adult learner with other languages under the belt so needs one that explains things at an intelligent adult level, but not afraid of grammar, kanji, or complex topics)
Most language books suffer from one or more of the following problems:
1) "Grammar is evil and must not even be mentioned." Either it is assumed to be too hard for your tiny brain to comprehend, or the marketing man says it turns buyers away. Either way you are left with a book about languages that attempts to teach you without the very tools you need to get anywhere.
2) "Oxbridge Ivy Uni publications" Superb as long as the teacher explains everything that isn't in the book. Well, you must obviously be at Univeristy with top notch lecturers, so all you need is a workbook, the teacher can do the rest. Just sit back and listen.
3) "I wrote this to impress other language teachers, not to teach you!" Where every topic must be covered in PHD level detail immediately else other academics will think the writer stupid. Concepts such as 'we'll explain that odd bit later when you know more, just learn it as is for now' are considerd heretical.
4) "Methinks thee doth need to elucidate eloquently." Nice book till you realise that whilst everyone understands you perfectly, they are sniggering as you sound like a Victorian professor. And when they speak you can't understand their modern words.
5) 日本語で勉強は僕の新しいでJapanese only. Hope you got the English guide and workbook, esle you are stuck at square one. Also hope you knew enough Japanese to make sure you ordered volume one, not volume 2 by mistake.