ext3 and ext4 do an admerable job keeping disks from getting fragmented, but when you're running file systems that full, there isn't much that can be done to keep it from getting pretty bad. Recently I heard mention that XFS, developed ages ago, actually comes with a defragging tool, so I decided to give it a shot. Backed up all my files onto every other hard drive I have sitting around, reformatted /home/, and loaded everything back on. Ran:
xfs_fsr -v -m /etc/mtab
and after it finished, tried playing a few videos off the hard drive, and you could barely tell that it was reading. Much better than the chatter fest that was ext3.
Granted, this isn't actually any kind of quantitative analysis of ext3 vs XFS, but it does seem to be quite a bit happier. I really need to just break down and buy a 1TB drive. All of my problems would go away...