Domain names...make sure you can edit TTL's on the domain records. This way when you point the domain records to other resources you can undo mistakes quickly.
Don't host the domain name at the host. Generally a bad practice.
Host...I definitely recommend using a Linux server solution. Windows has problems with both security and file upload permissions depending on how good or bad the admin is.
I have used quite a few LAMP hosts. LiquidWeb.com has been best so far. They say that they offer "legendary support" and I have found that to be true.
Don't worry about moving the site later...it's not as big a deal as it seems. You will never find a host that offers everything. Find a package that fits for where you are now and move when you need to.
Use strong passwords and change them every few months...one year tops. There have been exploits lately that take advantage of stupid passwords and passwords that have not been changed.
Change the password when you start the account. Usually the pw is transmitted in a plain text email.
Make sure you can install a SSL cert. You will likely want to have a backend that is password protected and secure. You may also want to have secure front end pages.
Make sure you have control over backups of your site. You will likely NOT want to download the backups through your ISP connection...too slow. If you can do a backup from one computer to another at your host it will move quickly.
I would personally stay away from the cloud. This is based on a bad experience with Media Temple. There may be some good cloud servers out there but I get a sense that they are generally a tad slow.
I have more to say but that's all I should put here.
