If you don't have a fireWire HD a USB one will work too (just slower). The trick here is to boot under the external drive so you can run Disk Utilities to repair if needed any problems and then using a defragmentation program defragment the HD. I do this on all my systems at least one a year (and some twice). The improvement can be great if you've never done it.
Adding memory also can improve performance quite dramatically. Given the cost I would do that next.
As to replacing the CPU Vs the entire logic board it's a matter of risk and costs. In either case you need to remove the entire logic board, then if you try to replace the CPU you need to get the correct one which can be very tricky if you've never done it before. The guide Jack pointed you to does not tell you what chip to get so you need to figure it out (the risk here is damaging the board if you get the wrong one). Given the price of a new logic board is not much more than getting the chip I recommend it that way for first timers.
But, were getting way ahead of what you should do first. Thats were I was leading you to, grab the low hanging fruit first then see where you are then.