A server load of 4 shouldn't be a problem....try installing eAccelerator (PHP script caching), because with these photo galleries they're parsing a lot of code.
I had a Gallery2 install hit *hard* by a popular forum recently and it ate up dual Xeons with no problems - I didn't have any script caching setup. But that didn't cause any slowdowns, because each request doesn't take long and there's plenty of spare CPUs around with HyperThreading.
The key to servers is cores cores cores - concurrency is important
But if the server load is only 4 and it's just CPU usage then that's fine, it just means the srever is actually doing something....double-check your Apache settings, you might want to enable KeepAlive and check the max servers and minspareservers, and so on.