I also recommend to start with Genki I (and WaniKani). You have to buy the book itself, but there are quite a few additional free materials to optimize the whole process for self-learners (e.g. sethclydesdale.github.io).
If Genki isn’t right for you, then Minna no Nihongo (ISBN: 978-4883196036) should be comparable.