Set all video settings to the minimum. It won't detract from your experience at all. Also, since this game is single-threaded and not really multicore, it might help to lock programs like Firefox and IRC to one core (say Core #0) and to lock Sins to another core (say Core #1). You can also set Sins to high priority. Also, you should close any other programs you have open that you are not using.
Most of the problem in online multiplayer will come from other people. You can see who the lag culprit is by opening up the Network Window (F5 is the default key). Most experienced players have already reduced their settings and know the drill, so I think the problems are normally caused by newer players. Also, sometimes ICO itself will lag and people can also get some lag on the Internet that has nothing to do with their computer or settings.
Also, your best bet is to play with Small or Normal fleet sizes on smaller single star maps. Consequently almost all online multiplayer games amongst the pro crowd are played on single star maps, normally the random single stars.
