There was another thread related to this a while back.
https://forumosa.com/taiwan/viewtopic.php?f=25&t=104919I've found that franchised cafes like Dante Coffee, Mr Brown, etc. to be sufficient.
Some places it is better to buy the Wifly card, so you have access at Starbuck's, Burger King, KFC, etc.
http://www.wifly.com.tw/Wifly7/en/Last time I was at Eslite in Xinyi, they had open wifi, but I could not connect to it.
My guess is that there were too many devices connected to that access point.
If you don't mind Taiwanese food cafe, there is a neat little place near Guting MRT called Mix Coffee Tea.
https://plus.google.com/107553815111965833231/about?hl=enThe food is not the best, but they have free wifi and the upstairs is pretty quiet.
Edit: Here is the info for the Taipei free pubic wifi network
https://forumosa.com/taiwan/viewtopic.php?f=7&t=105278#p1379141