If anyone has any suggestions / reviews, I could use them. Otherwise, the three webhosts I'm looking at are:
http://www.totalchoicehosting.com/web-hosting-plans.html - fast support. Most used from this MT forum: http://www.sixapart.com/movabletype/forums/index.php?showtopic=28301&hl=good,and,hosting&st=0
http://he.net/hosting_prices.html - Geeky, to-the-point, but expensive. Got gcc though, and are open to BitTorrent running there, which means they support other cool stuff. Probably includes most unix tools.
http://www.phpwebhosting.com/ - Expandable space, unmetered bandwidth. Perl modules installed on request. SSH included. Crontabs, firewalls, unix tools.