The easiest way to find out if a host meets the recommendations is to upload the autosetup.php file and visit it -- the area at the top will show whether anything isn't meeting recommendations.

WSN requires PHP 5.2.0+ and MySQL 4.1 or higher (or equivalent fork like MariaDB). In order to take advantage of URL rewriting you need an Apache or litehttpd webserver, which basically means any non-Windows web host. If you're interested in converting attachments to FLV, the host will need to either already have or be willing to do/allow the install of ffmpeg. If you need thumbnail images generated of PDF files, make sure the host is willing to provide ImageMagick.

Try to make sure your host runs PHP and FTP as the same user.

If you have any of those, permissions will be handled automatically for you. If you don't have any of them, you'll have to spend a lot of time setting permissions manually. If you don't know how to find whether you have one of these, just email your host to ask.

The GD library is also important to have for the security image and thumbnails, though virtually everyone will have it since it's bundled with PHP by default these days. If possible, the bundled version of GD is better than the external version since it makes the image_rotate function available.

A few hosts disable both fopen url wrappers and curl, effectively cutting off your server so it can't download files from elsewhere. This will make things harder for you by disabling the automatic upgrade.