>>20
Mandarin is the first language in taiwan, especially taipei (where I studied). Most taiwanese can also speak 台語, but it isn't commonly used by younger generations. It seemed to me that knowing 台語 was primarily a way to maintain cultural heritage or speak to grandparents.
I wouldn't call their mandarin accent strange. Sure, there are some slight differences, like pronouncing 是 and 四 identically, and I find they sound a little mumbly, but it's nothing major.
I understand where you're coming from- I was apprehensive about that before going to taiwan. But when I actually went to asia I realized that they might call the beijing dialect "standard" but that really doesn't mean anything. There are differences in pronunciation all around china, and the difference between taiwanese and chinese PTH is definitely not enough to rule it out as a place for learning mandarin.
If you're interested in going to asia to learn chinese, remember that you're probably going to have a white person accent more than anything. So don't worry about what accent they speak with, and go wherever excites you.