I'll put in my two yen, and vote for the 'Genki' series by the Japan Times; I started with a completely different set of books, and when I switched universities, moved from the 'Learn Japanese' texts to the 'Genki' texts, and was amazed at how well-written they are.
You'll be required to learn how to write, of course, because by the third chapter of Genki-I, everything is in kana, and they slowly begin introducing kanji at a rate of about 15 per chapter. While this might feel fast at first, it starts to feel slow once you get about halfway though the second book, and by the end of the second book, you're probably just picking up kanji on the side anyway (yeah, like I'm going to need to ever write 殴る).
Vocab is topical, grammar explanations are well-written, and it's definitely suitable for self-study, although on that note, I recommend at least taking a semester or two at a local community college. Why? Because just interacting with a native speaker on a daily basis will give you the a big boost on being able to pronounce things correctly. Nothing is sadder than a book-taught gaikokujin who can write Japanese almost fluently, but who sounds like a bad anime when he-or-she talks.