Beginning last night, I reinstalled my laptop. Normally, if it were just to clean up some packages, I wouldn't do this - the aim was more to try out removing the disk encryption that I was using, and the effect has been quite dramatic.
I worked out a while ago that the device-mapper encryption was slowing down disk access - with it gone, boot times are much shorter (and I don't have to type in a LUKS passphrase). GNOME loads a lot faster. Additionally, bash starts a lot quicker than it did. I suspect loading the bash completion routines takes quite a bit of disk access. Update: No, I just didn't have the bash-completion package installed. Bash is still slow. GNOME is still faster, though... for now.
So, I will probably keep my new install. I need to investigate encrypting a USB device and integrating that nicely with GNOME and gpg.