Website is unresponsive

With that many listings, I would definitely go dedicated server, based on where your majority target audience is.

However, when checking your site there was one main issue I see that is you were trying to load all markers in the one map with zero clustering.
This was basically doing two things.
1. Maxing out the browser memory by trying to show so many icons on a map.
2. Causing a broken PHP session if the server failed to load all the markers in the max server timeout time.

I have installed our marker cluster addon and set it to use server-side clustering, you should only ever have it set to that, client-side will have the same issues as above.

Thanks,

Stiofan