First of all, keep in mind that work_mem is per operation and so it can get excessive pretty quickly. In general if you are not having trouble with sorts being slow I would leave work_mem alone until you need it.
Looking at your query plans, one thing that strikes me is that the buffer hits are very different looking at the two plans, and that even the sequential scans are slower. I suspect that the issue has to do with read-ahead caching and having less space for that. What this means is you are biasing memory for re-use of indexes and against reading tables on disk.
My understanding is that PostgreSQL will look to the cache for a page before reading it from disk because it doesn't know really whether the OS cache will contain that page. Because the pages are then staying in the cache and because that cache is slower than the OS cache, this changes the sorts of queries which are fast vs the sorts that are slow. In fact reading the plans, aside from work_mem issues, it looks like all of your query info comes from the cache but it is a question of which cache.
work_mem: how much memory we can allocate for a sort or related join operation. This is per operation, not per statement or per back-end, so a single complex query can use many times this amount of memory. It isn't clear you are hitting this limit but it is worth noting and being aware of. if you increase this too far, you lose memory that might be available for the read cache and the shared buffers.
shared_buffers: how much memory to allocate to the actual PostgreSQL page queue. Now, ideally the interesting set of your database will stay in memory cached here and in the read buffers. However, what this does is ensure that the most frequently used information across all backends gets cached and not flushed to disk. On Linux this cache is significantly slower than the OS disk cache, but it offers guarantees that the OS disk cache dos not and is transparent to PostgreSQL. This is pretty clearly where your problem is.
So what happens is that when we have a request, we check the shared buffers first since PostgreSQL has deep knowledge of this cache, and look for the pages. If they are not there we ask the OS to open them from the file, and if the OS has cached the result it returns the cached copy (this is faster than the shared buffers, but Pg can't tell whether it is cached or on disk, and disk is much slower so PostgreSQL typically will not take that chance). Keep in mind this affects random vs sequential page access as well. So you may get better performance with lower shared_buffers settings.
My gut sense is that you probably get better, or at least more consistent, performance in high concurrency environments with larger shared_buffer settings. Also keep in mind that PostgreSQL grabs this memory and holds it so if you have other things running on the system, the read buffers will hold files read by other processes. It's a very large and complex topic. Larger shared buffer settings provide better guarantees of performance but may deliver less performance in some cases.
Best Answer
I usually prefer to start with lower shared buffers on both Linux and Windows, and keep work mem low also. Maintenance_work_mem can be left generally the default too. Keep in mind that too low a maintenance_work_mem may slow down db restores but it won't stop it. Generally you are better off starting low and then tweaking upward to find sweet spots than starting too high and working your way down.
Secondly you are reserving half of the memory on your box for PostgreSQL and only PostgreSQL. This can have very unfortunate side effects if you are doing anything else. Since this is Windows XP I am assuming it is not a dedicated server, and you are going to do far better with conservative settings here.