Need for Speed- WMPS Quite slow

What can we do to improve the speed of our WPMS installation. We've been dealing with slowness for a few months now.

We added W3 Total Cache for a bit, which helped at times, but it made us vulnerable to a malware attack.

We host on a remote server. Can you make any suggestions to improve page calls? Plugins? Permissions?