Running out of memory on contact creation
What is the default dedupe rules you are using? is this the standard ones or did you customise?

In general, the performance problems I experienced on civi the same size as yours are

1) badly configured server (eg mysql with wrong variables...). I would recommend you to run mysqltuner, you need to read the doc before blindly following their advices, but it's mostly good
2) modified dedupe rules (this one is a performance killer)
3) smartgroups (easy to kill your server with that one too)

It's probably worthwhile to check the load of your server and mysql configuration in any case, but dedupe rules are usually close next indeed