1) 123systems.net is a great provider.

2) If you've never used linux EVER, I highly suggest getting a Windows VPS instead (which are much more expensive though) or at least a managed package (again, more expensive). Otherwise, there is a STEEP learning curve and most people give up. If you didn't know this already, the vast majority of us do not have a UI for our linux VPS'....we do everything via command line (like command prompt in Windows).