If you don't need a ton of bandwidth, I really suggest you checkout linode.com
You get a clean install of whatever linux OS you want, and you can delete and reinstall the OS anytime you want, reboot etc. It comes with nothing so you install what you want yourself. Starts at $20 a month, it's great for messing around getting things going.
Then I'd move to something dedicated for a big live site. But linode is the best for getting things going
Oh, and there's slicehost too, but I'm not sure if they are as good since rackspace bought them.