Completely depends on what you're doing--what kind of app you're building. A very good middle step is a VPS, which looks like your own server (full root, shell access) but is actually a virtual server on another box. With the latest virtualization in Linux this is a really good way to get cheap computing power.
You can even get hosting companies to provide fully managed servers, which means you just give them the app and they make sure it's always running and healthy.