What is the first recorded contact with Taiwan by Europeans?

A book chapter by Rui Manuel Loureiro, in the book Taiwan - A Bridge between the East and South China Seas, Angela Schottenhammer (ed.), 2011, addresses these questions in detail. It's difficult to pin down exactly when the island was first named by the Portuguese (initially Lequio Peqeno, it seems Ilha Formosa came later) or physically seen (possibly decades after appearing on maps).

However, one key episode is well known:

The first documented Portuguese landfall on Formosan territory occurred in July 1582, when a large junk outbound from Macau, under Captain André Feio, accidentally ran aground near the south-western tip of the island. Several Jesuit missionaries who were on board, on their way to Japan, later wrote accounts of the journey, including Francisco Pires and Pedro Gomez, and also Alonso Sanchez [...] The mixed group of about 300 people, including, among others, Portuguese, Chinese, Spanish and Japanese, stayed on the coast of Formosa for several months, until they were able to built [sic] some improvised sailing craft, on which they made the journey back to Macau in September of the same year. During their forced residence on the island, they came into contact with the local population, whom the Jesuits describe in some detail.

So far despite a claim in the question I don't see any sources putting Dutch sailors or traders in the area until the 17th century.

From [1]

These rutters ... allude to Formosa, sometimes under the sobriquet of Lequeo Pequeno (Little Luchu), since the distinction between the Ryukyu Islands and Formosa was not always clear to the early navigators, and sometimes under the more modern name. The Portuguese, although they coasted the ... "Beautiful Isle" often enough, never ... explored it at close quarters. ... The first recorded visit was ... the shipwreck of André Feio on the western shore in July, 1582

"the Beautiful Isle" -> "Formosa" means beautiful

A rutter (from the Portuguese roteiro) is a long, detailed, text describing, step by step, what could be seen from the ship during a trip. Natural features such as mountains and isles were described, so that the captain might recognize them, as well as latitude and current measurements, and perils such as rocks or sand banks. Rutters were more valuable than maps and often highly secret.

What the book means, in context, is that various rutters described Formosa (as seen from ships), but it was often confounded or conflated with the Ryukyu Islands (a chain of islands which start close to Formosa). As the Ryukyu were called Lequeo, the latter is not really an alternate name for Formosa, it is early inaccuracy.

André Feio translates as Andrew Ugly. It may have been a nickname.

[2] is a book from a missionary bishop. He says the Portuguese first saw Taiwan in 1590, although [1] tells us that, if you consider the naming confusion alluded above and read the rutters carefully, they probably had described Formosa in the period 1550-70.

A Spanish Dominican, Fr. Juan Cobo, went and died there in 1592 (it is not clear but it appears to be another wreck and not an intentional mission). Finally, after the Dutch settled in the south, the Spanish tried to settle in the north in 1626, but the mission was unsuccessful, with native massacres and expulsion by the Dutch.[2]

Finally, [1] also claims Taiwan to be terra incognita for Chinese and Japanese during the 16th century, but there are registers of two Japanese ships trading with Formosa in the first decades of the 17th century. Not sure if before or after the Dutch settled there.

Plus: Do not expect Portuguese travels in the Far East to be always as well recorded as the most famous ones to America or India, with full ship lists and many names known among the crew. The Far East was too far for direct sailing.

They would refit in Goa and/or Malacca, with a partially Asiatic crew (some of the rutters were even written by Gujarati navigators), and much administrative / supply / repair / personal management work was done there. They even used locally made Asian-style ships, specially to less important local trade. Many details were lost, or at least, to find them you would have to dig much deeper than general history books. [1] have references to collections of original rutters, e.g., although it is not an easy reading by any means.

[1] The Christian Century at Japan C R Boxer 1951 UCPress and Cambridge UP

[2] Christians in China Jean-Pierre Charbonier 2007 Ignatius Press (Original 2002 Histoire des Chrétiens de Chine, Les Indes Savantes, Paris)