Well, in this life you get what you pay for
If you want a really s-l-o-w server that dies a lot get a free one.....
Otherwise I'd suggest www.dsvr.co.uk
£300 UK Sterling gets you a complete 300MB Server that's PHP and MySQL enabled, you can set up up to 300 domains on it, 300 email accounts etc.... full telnet access - the works!!!
If you're serious about what you're doing the £300 is a small price to pay for so much - I've been using them for years and can only pile on the priase for them.
Dave