Your 64MB Intel Graphics doesn't seem like enough power to me. If you were to spend $59 on a
GeForce 8600GT you would notice a dramatic improvement.
What model Celeron do you have? Celeron is like a value grade Pentium, so if you were to replace that with a Core 2 Duo/Quad or Pentium D (depending on what is compatible with your motherboard) you would als see a great improvement. Video card would be a quick fix, but you need to make sure your power source can handle it. What is the make/model/wattage of yoru power source aka power supply?