There are many many many providers that provide Linux VPS'es, but most of them don't have OS Templates with a GUI. With linux this isn't a problem, because you can easily install it yourself.
When it comes to providers, there are many, so please specify for what your planning to use it so we can recommend one that fits you.

Some time ago I used KnownSRV USA VPS, I honestly don't know if he still sells those, if you have a small budget you might want to look at Burst.Net (They do have OS templates with a GUI), but their VPS'es come with little disk space, and only the "premium" ones have a 1Gbit/s uplink.

Again, if you can specify what you want to use it for, we can help you better.