Each Linux system is currently running a different version of the kernel. Today LMDE is on 3.2.15 and Arch is on 3.3.3, on the weekend when I ran my tests Arch was on 3.3.2. There doesn't appear to be an improvement in the internet speeds on Arch since the upgrade. I have been experiencing this since at least version 3.2.12 on Arch, I do not recall which version LMDE was on when I first noticed the slower speeds.
It is slow in both Chrome/Chromium and Firefox. I haven't tried Opera, although I would guess it would be the same. It is also slow loading images in my RSS reader (RSSOwl, which I believe uses the XULRunner for its backend) and both apt-get and pacman updates are running noticeably slower than they used to. So, I think it is a lower-level system issue and not specific to any one program.
I should note (I forgot to mention this in my previous post) that it appears that the slowdown is in actually negotiating a connection with a website/server. If I am downloading a large file through the browser, it can take up to a minute to start the download, but once it starts it downloads at my ISP's advertised speed of 20 Mb/s. Same thing with streaming video on YouTube, it takes a long time to start playing a video, but once it does I have no trouble keeping up with buffering at 720p.
I have never explicitly enabled IPv6 in any of my OS installs, although the Arch wiki says that it has been built into their builds of the kernel directly since 3.2.6, so it is probably enabled there. I cannot find as clear information about it on the Debian wiki, but it does say that IPv6 support was a release goal for Squeeze. Since I have had the same LMDE install since January 2011 and the internet slowdowns have only happened in the last few weeks to a month, I am uncertain if IPv6 is to blame, but I will try disabling it to see if it makes any difference and report back.
Thanks for your help, if you have any other ideas, I'm open to them!
AMD Athlon II X4 630, 4 GB DDR3 RAM, Nvidia GeForce GT 430 - 64-bit LMDE (Gnome3) tracking testing, 64-bit Archlinux, 32-bit Windows XP
Aluminum Unibody MacBook - MacOS X 10.7 "Lion"