Which distro are you using mate? Some popular ones like Fedora, Suse, Mandrake unfortunately are not at all optimised for speed, and can feel really slow, slower than even windows XP, with its eye candy turned on.
But this is not too difficult to cure, first of all, the biggest bottleneck in linux performance is the Desktop Environment / Window Manager. You will probably be using Gnome or KDE, which are unfortunately quite slow. This is especially true for Gnome. I have no idea what made Gnome, GTK, Pango etc all become much slower immediately with version 2.0 :\ anyway, the simple solution is to use a different environment. Maybe
XFCE. This is a very fast and good looking gnome-like desktop environment, it will provide a remarkable improvement in performance.
You can also opt for a plain and simple window manager like fluxbox or icewm. This will be
much faster than any desktop environment, but the tradeoff is a lower level of integration.
And now what is important is the number of services loaded up while booting. As batty said, many distributions install things like http servers, ftp servers, which are automatically loaded on each boot. The simple way to disable these varies from distro to distro, but you can probably configure your services using the tools "chkconfig" and "ntsysv" if you use a redhat like distro. Type "man chkconfig" etc. in a terminal window to know more about each.
And lastly, tweaking linux turns out extremely easy after a little patience at first. You just can follow the /etc/inittab file and see whatever initialisation scripts are being run by the system, and modifying them at will.
Also, if you want a very responsive distro out of the box, try
Vector Linux.
And finally, don't worry, the sluggishness is not a problem with linux, but with most modern distro's. My slackware box on 266MHz, 128MB RAM runs as smooth as XP on a 2ghz, 256MB RAM machine
hyeah:
)
then there are distros which are also optimized for slow computers, slackware rocks on this front 
