The two main companies I am looking at are rackspace and oneandone. The former costs more for a dedicated box but I have a lot of faith in their support and reliability. The latter is cheaper but has plenty of bandwidth and a bunch of bonus stuff.
I was also looking at credit card processing. In particular I was looking at datacash as they provide a test server and a perl api.
Anyone dealt with these people before ?