I recommend edgehosting, which is the paid hosting arm of edgenetwork.
Edge is run by 5 guys at various colleges (myself at UIUC, Purdue, etc). We have 11 some odd servers for the network, and 2 for the commercial hosting portion (actually there is a 3rd, but its dedicated to just one hostee). I'd recommend ourselves because we're johnny on the spot with support requests.
Gentoo/Red Hat/FreeBSD are the boxes we run on. We support PHP 4.X, Perl 5.X, MySQL 4, Postgres, et al. We're real flexible with stuff you need installed, as long as its not an extravegant request, we'll probably put it on the server.
--
Chris "TunkeyMicket" Watford