For your Linux servers you might try SliceHost: http://www.slicehost.com/

Note: I have not used them, but will probably use them in the near future for an enterprise I have in mind. You can probably call them and ask for references, or cull references from their blog: http://www.slicehost.com/blog/