Better to start off with Slicehost, $20 a month:
Slicehost - VPS Hosting
Or, perhaps Linode, about the same money, but more bang for the buck:
Linode - Xen VPS Hosting
I refer Slicehost, but others like Linode better.
We use Slicehost for one of our servers and have been very pleased with it. We tried Linode and was disappointed, but it was perhaps my fault as I'm very impatient with services and expect them to work nearly flawless with perfect support. Slicehost has great support as well, so we are pleased with them. I really like their
chatroom support. If you have questions about their setup and prices, go there.
I do not recommend free hosting a new domain with someone like Godaddy where you don't have root and ssh access to the shell, and you don't have direct access to the database.
That is why I recommend users with a new domain and what to move forward go with a solid VPS provider who can easily add CPU power and RAM if your project is successful.