I started off with f2o, which is free: http://hostprogressive.com/webhosting/plans/f2o/index.php ; I liked it when I had it, but it's been a while. PHP, MySQL, Python, Perl. I haven't used it for 2 years though.

When I wanted a paid service, I moved to Joyent, and they've been awesome, but it's $15 a month. http://www.joyent.com/connector/pricing/ . You get SSH, any programming language you want, MySQL, and great customer support.