You do not need a dedicated server(although that would definitely be good!) - Shared servers are fine. We run our demos on a shared server! Performance issues are mostly related to specific server settings ...
I believe we fixed an issue the other day: Someone simply moved from windows hosting to linux hosting within the same server hosting company, and the difference was night and day.
I am not an expert in this field, and I think Pain may be able to fill in some additional advice. All I can say, is that having to wait 90 seconds(!) is simply wrong, even if you have a thousand pictures. The CACHE system we used should speed up performance exponetially, but it is often very slow the first time you view the gallery, because it is then it actually caches. Every time you click "Clear Cache" from the admin menu(which is sometimes required), you will have to re-cache from the gallery frontend, and that is often slow.
If you check your gallery a second time after cache is created, and it's still slow, then the issue is related to your server. Either it is not able to save cache, or there are some unusual settings on server hogging down the performance.
I did check your gallery, and I can confirm that it is horribly slow. The following script takes ages to load, although it should be mostly cached:
http://www.historysend.com/iv/?a=folders
What version of the gallery are you using? Perhaps you can provide us with login to your admin, and perhaps also FTP? That would help us look into your specific performance issue ...