Well if you're in the US, you might have a look at Hurricane Electric
he.net. They're $10 a month for 25M of storage. You do get shell, and their Perl is 5.8.0 at the moment. I've been using them with a couple of accounts for about 5 years and never had a problem. Their techs even helped me out on a few Perl scripts late one Saturday evening. Nice to have tech support 24/7.
HTH!
Revolution. Today, 3 O'Clock. Meet behind the monkey bars.
I would love to change the world, but they won't give me the source code