What wireless card or chip are you trying to use with Linux? I've never had any problems getting wireless to work on Linux. I've used either "ndiswrapper" or "madwifi" drivers. I use "wpa-supplicant" to handle the encryption and pass phrase authentication.
If you already have a broadband router, then you normally do not want to use Internet Connection Sharing (ICS). Just use simple network bridging on the Windows system to bridge the wired and wireless networks.
This is a good article on the subject of setting up wired to wireless bridges.
Linux emulation libraries such as CYGWIN don't see wireless network adapters any differently than wired network adapters. They communicate at the sockets level, not the Ethernet or wireless link level. It's up to the host OS (Windows) to handle the pass phrase authentication and encryption setup.
With a virtual machine program like VirtualBox you can run Linux inside a virtual machine on Windows. In that case the host OS (Windows) still handles the pass phrase authentication and encryption setup. The Virtual network adapter is bridged (in essence) to the wireless adapter.
VirtualBox also provides for USB pass through so you can use a USB wireless adapter directly from Linux inside a virtual machine. Then Linux will do the pass phrase authentication and encryption setup. The wireless driver in Linux will be used, as well as any supplicant software such as "wpa-supplicant". The main reason to do that directly to USB is for network hacking. It isn't any real benefit for normal Internet communication.
One's first impression of Linux is often affected by the hardware configuration. Linux supports some hardware very well, and has limited or no support for other hardware. Wireless adapters, sound cards/chips, software modems and web cameras are examples of hardware that may have limited Linux support. Support for Wireless adapters continues to improve for Linux.
Windows tends to support more hardware than Linux, but that Windows support is getting slowly worse as new hardware departs from long established standards. I've recently had problems trying to use Windows XP on newer hardware, or Windows Vista on older hardware.
Sometimes it makes sense to purchase hardware that is compatible with the operating system you plan to use rather than spending time trying to make existing hardware work. For example, I found that spending $50 on a hardware modem was a better investment than trying to make software modems work on Linux. The same thing may be true with some wireless adapters.
Laptops are more of a challenge but it often still pays to buy an external USB adapter for Linux than to try and make the cost-engineered hardware inside a laptop work. In addition to less hassle, the performance may be better.
If you don't want to spend time learning about Linux then selecting compatible hardware is much more important. Although some Linux distros can install and run without much configuration they don't do that on all hardware. If you're willing to learn more about Linux you will be able to support some additional hardware that requires extra work to configure with Linux.
I'm carefully avoiding the question of which is better for a server, Windows or Linux. There are advantages and disadvantages with both. The major disadvantage of Windows Server is the cost of licensing. The number of clients and the software on a Windows server have a direct effect on the cost. The disadvantage of a Linux server is the extra time and knowledge required to set it up and maintain it. Hardware support might be an issue depending on the requirements for the server. In some cases Linux supports hardware that is unsupported by current Windows versions.
With Linux there are a lot more choices, so be careful that you don't form your impression of ALL Linux distros based on trying a few of them on only one or two hardware configurations.
Windows NT 4.0 and Windows 2000 are the closest versions in terms of the performance and resource requirements for a Linux server. Newer Linux desktops may require something closer to a machine that would run Windows XP. Be careful comparing older versions of Windows to Linux because newer versions of Windows will not compare as favorably. If you upgrade a server from Windows NT 4.0 to a newer version of Windows you may have some of the same issues that you would with Linux.
Newer versions of both Windows and Linux eventually have problems with older hardware. That happens as new features prevent older hardware features from working, or the drivers and software for the older hardware become less common. Older hardware is often tested less in new releases and inevitably some bugs appear. Whenever the operating system and hardware are not from the same era, one should be prepared for problems. The life span of hardware and software is getting shorter and compatibility problems are getting much more likely when the hardware is not upgraded with the operating system.