So, kind of narrowed down to this:
http://myhosting.com/
-Renegade
Did you notice this part:
Multiple State-of-the-art Facilities
Our web servers are housed within Equinix and Earthlink Enterprise Data Centers located in Toronto, Canada and Rochester, NY, USA respectively. Web servers are directly connected to world-class fibre optic networks which ensure that your web site experiences superior performance in a fully-redundant and secure environment.
This is why I didn't make any recommendations; even the company I used to go with that was based out of Australia had datacenters in the US. If you're concerned enough to be doing this, it seems like this would be a red flag...
Still mulling over a control panel... I don't like the idea of subscription software. I like to pay once and be done with it. So, the Plesk and cPanel pricing just rubs me the wrong way.
-Renegade
If you're paying from hosting from a good provider, that cost of cpanel/whm should be a part of your hosting price- not a separate charge, truthfully. You can get things a la carte, but if you don't you'll find the cost of a reliable host with/without cpanel not to be much (if any) different- and a lot less painful if you aren't in the know regarding *nix.
If you do want to go the more painful route, we aren't looking at anything like RDP- more like command line stuff. There's not a desktop OS to any of this stuff AFAIK. I think your prejudices against subscription software might be making you look at this the wrong way- especially since you're going to be paying for hosting per month in any case.
FWIW, if you're primarily interested in more of a webmail solution (which is probably smarter if it's your server) take a look at Roundcube. I've been evaluating it and it's very impressive.
-40hz
I have roundcube on my server, and it looked pretty cool, along with horde. My personal favorite though is squirrelmail for a client.