Windows vs. Linux Hosting Services
If you are not doing live "in situ" updates via the extensions, nor using the FrontPage style HTTP import and export, then you will need a means to upload your pages and other website files to the server after you complete them. The most common way to accomplish this is via the "File Transfer Protocol" (FTP). From the System Administrator's perspective, there are differences in the ease of setting up FTP for individual users that tend to make it more commonly available of Unix servers than it is on Windows. If FTP is important to you, you will want to check specifically for this feature.
While Telnet access can be provided on a Windows server, it almost never is. Far more common on Unix servers (which is where it originated) it is, however, quite rapidly disappearing from them too because of security considerations. Telnet is useful to you if you are familiar with the Unix or Linux command line utilities and commands and wish to use them for controlling or manipulating your files. Almost everything you do with your site through a Telnet session can be accomplished by other means, which means that the availability of this feature may not be of particular importance to you.
CGI - Shell Scripts and PERL
The "Common Gateway Interface" (CGI) provides a means to connect or link from a web page to a program written in a scripting language that runs on the server. Some people refer to a "CGI Script" when what they actually mean is a Shell Script accessed via the CGI. Shell scripts are files containing a series of commands to be executed by the Unix Shell. They are therefore a feature of a Unix or Linux system. Other types of scripts accessed via the CGI include PERL scripts. PERL is readily available for either Unix/Linux or Windows. It is included by default is almost every Linux distribution and is an add-on to Windows. As a very powerful and popular scripting language, it is available on most hosting service systems. It is something that you will want to check, however.
Server Side Scripting - PHP, ASP, ASP.net
There are many other type of Server Side scripting and/or interfaces, including PHP, ASP and ASP.net. PHP, as an easy to learn, but very powerful scripting language has gained a great deal of popularity. It is readily available for both Unix/Linux and Windows systems, but is still more commonly deployed on Linux. Most hosting companies these days will have made PHP available on their systems no matter which platform they have chosen. It is still, however, something you will w3ant to check on if you have any plans to use it.
ASP and the newer ASP.net are native to Windows. They provide, among other things, access to Visual Basic and the VB Scripting language. I have seen ports of ASP to Linux, but it is very rare to see it offered by a hosting company running Linux servers. I have not personally tested the capabilities of the Linux ASP implementations and so can not advise you as to how compatible they may be. ASP.net holds a great potential for the future of the web, providing features that greatly extend the capabilities that web developers can offer to their clients. A decision to utilize ASP or APS.Net may be a deciding factor for you in the choice of platform you look for in a hosting company.
Databases - MySQL, Access, SQL Server and others
MySQL is a common database on Linux based servers these days. It is also available for Windows and is starting to appear on the list of offerings from more and more Windows based hosting providers. Access, as a Microsoft product, is available for Windows. Other databases, including the large database systems such as SQL Server and Oracle can be accessed through interfaces such as ODBC. There are also ODBC connections to such system as the IBM AS/400, which is fairly common in medium sized businesses. These interfaces, which are fairly specialized, are more commonly available on Windows systems, and in the offerings of hosting companies are usually special request or custom solutions. If you have a need for such a connection, you will need to talk to the potential hosting service representatives.
Recent advances in operating systems, and especially in the areas of inter-operability, have brought the available feature sets of Windows and Linux based website hosting offerings much closer to each other. Where in the past there have been cut and dry advantages to one over the other for particular applications, these differences have now diminished to the point where the choice of operating system a hosting service company makes is frequently not a concern to the client. With a few exceptions, as noted above, you can often make your choice of hosting company based on the available feature set and factors concerning the company themselves, rather than the operating system they have chosen.