The solution in my case, was deleting ~/Library/Safari/history.plist. I did so, and then my Safari was back to loading pages faster than my 2.4 GHz P4 PC (IE or Firefox), thank you very much.
Here's how I tracked it down. In the Terminal, I ran this command:
$ sudo fs_usage -f filesys
I noted a number of hits to the history file, and decided to delete it. You could, of course, use sudo fs_usage for a broader monitoring of what is going on behind the scenes. From man fs_usage: "fs_usage -- report system calls and page faults related to filesystem activity in real-time."
[robg adds: I don't think this is necessarily specific to 10.4.2, and I haven't noticed any slowdowns here despite a full history file. Still, perhaps this will help someone else, so here it is...]

