Taiwan is full of great food, like some others have suggested, Ding Tai Fung is a must go to restaurant for their amazing food and quick service. I've been there in Taipei and Beijing and they're all great.
Some of the foods you should try:
stinky tofu: (tzo do fu)
egg/oyster pancake : (ou ah tzen) this is my favorite
meat inside a gelatinous oval ball, fried and smothered in a sweet/sour sauce: (ba wan)
fried chicken patties the size of your head for $1
airy shaved ice...