My experience with Linode

For what it's worth, a few comments on things you mentioned:

1.) You can switch to annual billing if you want to – I don't think there's a button for it, but you can file a ticket.

2.) Linode uses local disks. Presumably they use fast drives, but having to share leads to less than perfect performance. Or, perhaps you caught it while another user was swapping, or a backup was running or something. (Which really just leads back to the sharing thing.)

3.) Backups cost 25% of the plan, so if you're on the $30/month plan, it would be $7.50.

4.) There isn't any load-balancing, yet. Well, there is, but it's in beta. Seems like it's going well and will probably be released soon, though.

5.) Lish works with pv-grub kernels, as long as you configure it properly. Or it should, anyway.

6.) The à la carte upgrades aren't extremely useful, since they're priced so that you should upgrade to the next plan anyway. Though they do save the short downtime that upgrading entails (since you're migrated to a different host server).

7.) Finally, the 768 actually used to be 540 MB of RAM, not 512. :P

I don't mean to sound critical or anything; just figured you'd be interested to know.

Edit: typo