I am currently using a Linode right now and it is great. You get full root access to your virtual server which is great. If don't have any server running experience they have great documentation to help you get started. If you get the 512MB plan for $20/mo you should be good to go until you get a whole ton of users.