Welcome to WebmasterWorld Guest from 22.214.171.124
For example, if your site uses static files most of the time, I don't think there will be a major difference beetwen one and the other. However, if you plan to use ASP or ASP.NET, you must choose Windows. Personally, for PHP, Perl and Python I would use a Linux hosting (but this is a personal choice.)
Probably the most remarkable advantage of Linux-based solutions (more precicely, of Apache-based solutions) are .htaccess files, which allow you to easily configure the server (despite its use being sometimes discouraged as has some impact on the performance of the server.)
If your hosting company does offer you SSH access, and you are familiarized with a Unix shell or you are interested in learning about it, Linux is a good choice, because the shell environement usually is very powerful.
You should give some more information about your site to see which is preferrable.