When I started learning Taiwanese, I used 哈佛臺語101. The author apparently wrote it while instructing a Taiwanese language course at Harvard, but it's not a difficult book by any means. It uses stories, lists, dialog, songs and translations, and phonetic practice to learn spoken Taiwanese. The book comes with three CDs and the book itself, and I highly recommend it.

Also, it uses a tonal marking system to try and help you learn the eight tones. As for romanization, it uses a mixture of Tai-lo and POJ, but it fairly effective and easy to pick up. If you search for videos on YouTube, there are supplements for the book, and the book's website has the first ten chapters and additional resources.

This is nt$600.

I have also used 大家來學臺語, which also comes with a CD. I use this book for additional vocabulary and sentence/structural practice. It uses a romanization system that I'm not sure how to name, but once you get a foundation in Taiwanese, this book is easier to use (like I said, it's a supplement). It uses pictures for vocabulary and sentences for practice.

This is nt$350.

For speaking drills, Glossika has a Taiwanese fluency package that uses language drills and a supplemental PDF guide to help you in learning.

This is nt$2,320.