Slow Half-Life multiplayer performance

[Liquid Snake]

Half-Life runs rather slow in multiplayer. My fps cap (fps_modem) is 30. Often, the framerate drops to like <20fps when i get into any fight. In single-player, it runs great (always above 40fps in 800x600). I know multi-player is supposed to run slower since the CPU also has to handle the extra players. But 15fps, even in 640x480? Could it be my connection (56k with rate of 4500)? My netgraph tells me the rate is cutting out lots of info (often lots of yellow). I run TurboGL with 5.41 (plan to try beta drivers soon). Direct3D runs even slower, and the text is blurred. I used to run with gl_texsort 1 and gl_overbright 1 (since i found things to be too dark). From what i know, gl_texsort 1 changes the way the graphics card procceses textures and turns of multitexturing. I've turned them both off, with very little increase in performance. Are there any other settings that can help me?
My system:
P3-550
256MB PC100 SDRAM
G400MAX
MX300 soundcard w/ A3D on
3Com Courier Analog modem
Quantum Fireball KA Plus 18.2GB w/ Promise Ultra66

The settings i use:
gl_ztrick 0
gl_dither 1
gl_texturemode GL_LINEAR_MIPMAP_LINEAR
gl_polyoffset 5
r_decals 800
lambert 1
brightness 1
gamma 3
gl_texsort 0
gl_overbright 0
cl_himodels 1
fps_modem 30
rate 5000
cl_nodelta 0
r_netgraph 1