Hi, Michael. I think any of the GAME servers are suitable to run Spigot. Check the servers here:
http://www.soyoustart.com/en/innovat.../game-servers/. Currently they are out of stock, but they may replenish at any time.
If you choose Linux for your server, the first connection method you will have will always be via SSH, that is, using PuTTY. Once connected to the server, you can proceed to install your software. For spigot, you may follow the instructions on their web:
http://www.spigotmc.org/wiki/spigot-installation/. If you are not familiar with Linux administration, I'd recommend some simple distribution like Debian.