The package php5 depends on having either apache2 or cgi installed.
The two main options to satisfy this dependency is either libapache2-mod-php5 or php5-cgi.
If you remove one, the system will install the other, otherwise php5 would have an unmet dependency.
You can see the dependencies at php5 in the Ubuntu packages database.
As you probably already know, in Linux packages may specify "dependencies", that is other packages that must be installed in order for this package to actually work. These dependencies are resolved recursively, that is dependencies of your package dependencies are installed as well. This way meta-packages may exist that will install entire set of software. Common examples are libreoffice (for office suite) or kde-full for entire KDE desktop.
When apt (Debian package manager) installs some package, it marks all dependencies as automatically installed. This way it can distinguish between packages explicitly requested by user and packages that were pulled in merely as dependencies (about which user most likely don't care at all).
apt-get autoremove looks up for packages that are marked as automatically installed, but which are no longer needed by any manually installed packages. These are often older versions of libraries (when version of library is in package name to allow different versions to coexist, e.g. libavcodec54 and libavcodec56) or packages removed from repository, but sometimes some useful application gets pulled in as dependency and then is removed. This happens especially when you first tell apt to install recommended or suggested packages, but then configure it to not pull in these packages as dependencies.
To remove package from list of packages considered for removal, mark that package as installed manually. You can do it using apt-mark:
apt-mark manual <package_name>
or aptitude (following commands are equivalent, use only one):
aptitude unmarkauto <package_name>
aptitude install <package_name>
aptitude install <package_name>&m
Finally, to get some context when these particular packages were installed, you can try searching their names in /var/log/apt/history.log files. These logs are rotated (compressed and put in separate file) monthly; to get the full archive, you can run (order will not be preserved):
cat /var/log/apt/history.log > /tmp/full-archive
zcat history.log* >> /tmp/full-archive
Best Answer
Right autoremove only removes packages that were installed automatically as part of other package installs. The things installed in the image are seeded and so all are basically considered "manual".
You'll probably get rid of most of them by getting rid of Xorg:
And then do another autoremove.
There will likely be other things that are left around that you don't need.. but .. really.. why not just ask your VPS provider for a server image.. isn't it a little silly that they even offer the desktop image?