Did you try adding the memory limit in the php.ini? A lot of shared hosts will allow you to create your own php.ini and you can set it higher in there.
The only time I’ve hit that error personally is during updates/plugin downloads. However, if your site gets any reasonable traction, you’ll want a new host.
