I'm currently walking (mostly) around Taiwan. When telling locals this, which of the many words for "walk" is the best to use?
"徒步環島" or "環島步行" is most appropriate for "walking around taiwan". 

"環島" is around the island.

great activity, how many days you need? and where're you now?

have fun :)