The memory on your graphics board (video card) should have nothing to do with how many players are in a game.
For large games you will need a fast processor, lots of RAM and a good connection.
Also try turning off footprints in the options to improve speed (really helped here with a 2000XP+, GF 4MX and 256 Meg RAM).
The graphics card only needs to display what's on screen at any one time, so shouldn't need to be overly powerful...
James