Currently I'm having trouble with a server running Magento, it's unbelievably slow.

It's a VPS with a few Magento installations on it used for development, so I'm the only one using them. When I do 4 request all 2 seconds after each other I'm finished in 10 seconds. Slow, but still within the limits of my patience. When I do 4 "concurrent" requests, however (opening 4 tabs in a row, very quickly) all four cores go to 100% and stay there for like a minute.

How is this possible?

I know that there are a lot of possibilities here, so any tips on how to make an Apache/PHP server go faster are also welcome.

It used to go a lot faster before, and I've also tried APC, but it kept causing problems (PHP errors, something with memory pools) so I've disabled it.

By the way, the Magento cache is off and compiling is also off. I know this makes Magento slower than usual, but I don't think a 60 second response time is normal for any Magento installation.

Virtual hardware:
4 Cores and 4096MB RAM
Swap is never used (checked with htop) 100GB disk space, of which 10% is in use

Software:
Debian 6 DirectAdmin and apache custombuild PHP 5.2.17 (CLI)

If you need more info, please tell me how to get it, because I probably don't know how. I do know how to use the command line in linux and the usage of quite a few commands, but my experience with managing a server is limited.