Improving template/rendering performance
I would check for File IO; what does profiling your site tell you. I had similar issues and created the http://drupal.org/project/imageinfo_cache module and my views performance improved a lot by reducing file IO.

Seeing that your on shared hosing, checkout this http://kpayne.me/2012/02/04/use-register_tick_function-to-profile-your-code/