Unlike many people, our Taiwan trip started in Kaohsiung in the south, and ended in Taipei in the north.
In the following map, the yellow pins are places we visited. Cities/towned we stayed overnight were: Kaohsiung, Taitung, Yuli, Taroko Village, Jiaoxi, and Taipei.
October is usually a good time to visit Taiwan, when it's not too hot, not too cold, and not much rain. Although this year was somehow unusual. In Taroko we encountered very heavy storms. But it's a rememberable experience!
Taiwan has a very good network consisting of buses and different kinds of trains. There is an "iPass Card", togeher with a few other cards, that is good for most transportation tools (excepts high speed railway). It's also cheaper than paying cash.
In smaller towns, you can rent a scooter. However, keep in mind about two things. First, you need to prepare an International Driving Permit in your home country; Second, some stores don't rent scooters to foreigners. If that's the case, just go find another store that wants your business.
If you speak English, there's generally no problem, maybe with help from some younger people. Metro and buses announce stop information in several languages, including English. Good news: Taiwan is considering to set English as the second official language.