We've gone through these things EXTENSIVELY...
The problem is not really the network connection (we ran 100/Full on some really good switches to no avail), but the processor.
Needless to say, setting the system to 800x600 at 256 colors helps, but it will still be sluggish.
We've started putting the RILO 2 cards in our servers. They're more money, but the mouse is MUCH less sluggish, and the performance is quite good. Still not as good as KVM or products like Dameware or Terminal Services, but a lot better than the v1 RILOs.
Another good option is the new Compaq 16x1 KVM switches w/ remote IP services. You can remote into the KVM switch via a browser and remote control 16 servers (connected via CAT5 instead of that huge KVM cable!!)
As for other performance tips, we're tried a ton of options and every setting, but still to no avail.