The tax does NOT include medical insurance. You're supposed to take out your own "zorgverzekering" (i.e. medical insurance) from a private company, although you can get a subsidy to cover the expense ("zorgtoeslag") if you have a low income. What you may be thinking about is AWBZ, a national insurance scheme for which you do indeed pay the premiums along with your taxes and that covers various sorts of long-term care, mostly for the disabled and the mentally ill.
In general, for some reason Americans imagine that European countries always have government-run healthcare, presumably because that's what Britain has. In fact, most European countries have hybrid systems, with insurance provided by private companies or in some cases unions, and heavily regulated and subsidized by the government.
As for taxes: while taxes in NL are indeed extremely high, there are loopholes for foreign high skilled workers ("kennismigranten.") My cynical public choice economist interpretation is that the Dutch government realized that this group of people is more likely to vote with their feet, inducing a different Laffer curve, and as such the taxation rate maximizing public revenue is a bit lower in their case...
As for finding housing: very strict rent control laws depress rents way below market rates, which of course means that demand outstrips supply and some allocation mechanism other than price must be invented. In the Dutch case, most rental property subject to rent control is owned by semi-public nonprofits, and their allocation mechanism is almost universally a waiting list. In the case of Amsterdam, there are many districts for which a 7 year waiting list is not out of the ordinary. While there is a blanket exception from the strictest rent control laws for properties with a monthly rent above about 650 euros, the city of Amsterdam has the additional problem that an even larger share of rental properties is owned by said semi-public nonprofits ("woningcorporaties") than in other cities. As an outsider looking to get a"vrije sector" apartment (i.e. over 650 euros a month and thus exempt from the strictest rent control rules) you're in trouble. Consider living in Amstelveen, which has a lot of "vrije sector" housing because it is historically run by the liberal party, whereas Amsterdam is historically run by the labor party.