Well it's not drastic. You either have to change your hoster or you have to change to a VPS/Dedicated Server.
Some hoster might look good on paper or theire website but theire service and the options aviable (like memcache, apc etc.) are horrible.
Most hoster suit theire packages for a large amount of customer and options like memchace, apc, php_memory limit the amount of customer per server, they actually don't give a shit about one less.
Maybe you should look for a VPS/Dedicated Server or a hoster with specific options and limited customer per server (1-20 is a good amount) specific php_memory, timeout time etc.
As example for the upcoming 1.5 you should have atleast 128mb.
About your Internal Server Error this can have many issues. Your shop self (bad module etc.) or your hoster. You should check your error logs.