Operating System for your hosting service
the most important influence on the features that will be available to you will be the Web Server system in use. On Linux systems, the Web Server offered is almost always the Apache server. On Windows it's the Internet Information Server (now "Service"), IIS. Apache is also available for Windows systems, but is not very frequently used by hosting companies using the Windows platform.
HTML, JavaScript
No matter which platform you select for hosting your site, there are some things that are common to all. All web servers are (or certainly should be!) configured to support HTML files and JavaScript. It is also reasonable to expect that every system offering hosting services these days also has an outgoing mail server (SMTP Server) set up and available to you. The lack of this could be a problem for you.
FrontPage Extensions
While their name suggests that are for enabling the use of FrontPage, the extension in fact provide a set of capabilities that is utilized by a wider range of software. FrontPage itself is a very useful web development tool. especially for someone with a less intimate knowledge of the actual codes used in website creation, but the server extensions also provide a number of utility functions that the website can take advantage of and they provide for a "post" method that allows a program (such as FrontPage or Visual Studio, among others) to "Open" the live site for updates in situ. These extensions, which can be a very important feature for you, can be installed on either a Windows or a Linux server.
FTP and Shell
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.
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.
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.
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.