I signed up for a Linode this month just in case I ever need use of a mail server/web hosting+root access/whatever on a whim, and was absolutely blown away with how quick it was to set up. Hands-down THE most intuitive and well-documented service I've ever used on the internet, for anything. No more NetworkSolutions-related aneurysms!
