It doesn't sound like the problem is a VPS or specifically a Rails problem. 800ms is a lot, and 300-400ms for a view with fragment caching is a lot. I have a completely unoptimized app in development with 20-item paginated lists of partials containing partials running on a VPS (linode) that renders the uncached view in 130ms. And this is with Haml, which is slower than erb, especially for nested partials.

I don't know what could cause the slow-down off the top of my head. Are there slow helpers? Also, IIRC, iterating over a collection to render each partial is slower than using render :partial => @collection.