I have read a recommendation which was stating that after installing one should remove some packages from the default Ubuntu installation, in order to have a more secure server. What are your recommendations for removal?
Ubuntu has a fairly strong security policy. This includes the requirement that a default install shouldn't run any network servers, listening for outside connections. As those are the cause for most recommendations to uninstall packages, the answer there is no.
However, uninstalling anything you don't actually need will certainly help. It makes the system simpler and easier to understand, and probably reduces the probability of a privilege escalation, should anyone manage to breach the defences.
Personally, I uninstall everything that isn't used by me or the packages I use.
The most important part is not what packages are installed, but which servers are running, especially those listening on an internet-facing port. Disabling or stopping servers which aren't used is an important first step. Offcourse -removing- such a service does serve as "insurance" that it doesn't get started accidentally somehow, so it might be a good idea.
For removal, the most obvious targets are any programs that come with suid-root executables, and aren't used. A bug in any of these programs will have the potential to allow any random local user to become root, that possibility goes away if you remove the program.
You can use 'find' to find such programs, in a terminal enter: find / -perm -4000 -print this will give you a list of all suid-programs on the system, it will take quite a bit of time with a large disc.
The mere existence of a program on disc which isn't suid-root, and that isn't being run, should not have any large impact on security. You might still want to remove some for other reasons such as freeing up disc-space and reducing clutter though.