I can vouch for dotBen's recommendation. I recently signed up with a VPS for the first time a year ago for a site I'm still in the progress of building. There are a ton of step-by-step guides and how-to resources that make getting up and running relatively easy and painless. You'll be overwhelmed by the options you'll have access to, but there's really only a handful of decisions you need to make to get started. Go for a Managed VPS and you don't even have to worry about keeping up with system upgrades and such.

There's of course, the added reward of having learned and accomplished something new.