[Cheese]

as above...must eat the Beef Noodle...and if you can find the parliament building downtown in Old Taipei there are a number of excellent old Beef Noodle places that are simply amazing.
You also want to get to Raohe Night Street Market to experience what a real crowd is all about. Try the Stinky Tofu...yes it smelss like rotten weeks old socks in a Hockey Duffel bag...just try it.
There is also two other spots in that market that are must haves. At the far end close to the Buddhist Temple is Baked Dumplings. They bake them in small ovens that are similar to Indian ovens for Naan bread etc....these dumplings are amazing. So are every other dumpling you come across and especially the poppy seed variety. There is alo a place half way through the market that has a shaved brittle and ice cream Pita type roll up...find it and eat it.
You also want to go for Dim Sum at Din Tai Fung at the base of Taipei 101 which is also a must see. Get there early for breakfast or stand in line...it is simply one of the best Dim Sum's anywhere.
If you like Sichuan food go to Kiki Restaurant. There are a few of them, they do not disappoint. Delicious.

As above get on the bullet train and head south..I recommend Hualien on the East side of the Isle...beautiful spot.
Kaohsiung City on the West side is also excellent and has food there you cant find elsewhere on the Island...jump in and try it.

You will love Taiwan...it is Humid and rains often...but always warm to hot.

oh and...just show up for the lantern festival