I'm very pleased with Linode. I haven't needed the support much, but when I need it they're very knowledgeable and quick in responding.

You said you want to pay around $25, which means you either get the 360 or 540 (the latter would cost around $30.) You can upgrade/downgrade at any time, so you could start with the 360 and see if you need to bump up for more RAM or whatever.