Based on your requirements, I would recommend a content management system such as
Drupal,
Mambo,
WordPress, or
MovableType. They come with clean, professional layouts, are fairly easy to install, allow you to add or remove as much content as you want quickly and easily, and they all come with a search utility built right in.
There are so many hosting companies out there, it's hard to convince you one way or the other, but I would definitely recommend going with any Linux hosting over any Windows hosting. Linux will give you more reliability, compatibility, and it's what most people use these days. Personally, after doing a lot of research, I went with
Bluehost, and I'm very happy with them so far!
Going with a CMS will get you a nice looking website in almost no time that is super-easy to manage.
