To start off, you might want to look at Virtual Dedicated Servers aka Virtual Private Servers. They are inexpensive compared to dedicated servers, but more secure than virtual hosts (assuming you don't do something dumb). Typically you will get root access, basic webserver apps preinstalled, and the ability to install your own apps. Like others have said, the hosting company will have access, but you will have better control than with virtual hosts like Yahoo etc.

Update: added links