Xen is pretty great about partitioning everything except for I/O. Network I/O probably won't be a problem for you (xen doesn't really start getting tripped up until you are well above 1G/sec. I /believe/ linode has a 10,000 packet per second limit on top of that, but that's a whole lot of packets. This is probably not your problem.) but disk I/O will be.
Cache everything. If you cache enough, and have enough ram, slow disk I/O may not be a problem at all. watch your linode to make sure you don't go over quota on your disk I/O allocation... maybe email support to make sure you are in the clear. My understanding is that linode has better disk I/O than I do because they have a process in place for limiting heavy disk users. (my understanding is that it's a good process, they warn you before limiting you and generally do it in a fair manner. I plan on emulating them in this regard. )
No two ways around it; I/O to spinning disk and virtualization go together poorly. What would have been a sequential access on a dedicated server becomes random access... and on a good day, that means 1/10th the performance.
If you are using a lot of disk I/O, a dedicated server is about your only option. Considering the prices nearly all American providers charge, if you plan on keeping it for more than 2 months, you are nearly always better off buying. (and that way you can buy better disk, too.)
Of course, if you aren't limited by I/O, or if you can solve the I/O problem using ram caches, then it might make sense to stay 'in the cloud' on linode or ec2 or the like until you are sure you are going to need the space long-term.