Don't even consider shared hosting, unless you're setting up a cheap Wordpress site you're better off going for Heroku/AppFog or even a VPS. Shared hosting tends to be slow, unreliable, the support usually sucks and all their promises about "Unlimited X" are bullshit.

VPS do need a lot more work (not sure if I'd call it maintenance) than a shared host since you'll be installing everything from zero and after that you're the one in charge of making sure it stays running. But again, even that if preferable to using a shared host.