Does WordPress run better on a Linux server than a Windows or does it matter? Any thoughts on which way I should go for launching a bunch of WordPress blogs?

Well, wordpress depends on PHP and MySQL, so if you want to have good performance, ensure that PHP, MySQL and your web server all run smoothly on whatever platform you want to use. There are known issues with Apache 2 on Windows, for example.

In the end, there are some things in PHP that work better in Linux, somethings that work better (or at all) in Windows. For example, the printer extension works only in Windows, etc. (this is just an example -- for example, you wouldn't use the printer extension in Wordpress).

For some themes and plugins that rely on GD/ImageMagick -- Linux works best. In the end, it all depends on what features you want to enable for your users.

I read that to use Permalinks you needed mod_rewrite in Linux.

Im not very familar with Linux hosting, is mod_rewrite a common feature with hots or would it be something special i would have to request or pay extra for?

mod_rewrite is an Apache-specific feature. If you were using Apache on Windows, you would have access to mod_rewrite.

IIS also has mod_rewrite-like functionality, but its a filter you have to pay for.

linux definitely has mysql/php and mod_rewrite (although may not be enabled) whereas for windows they are all extras. so check with your host :)