I can assure you that you are imagining the speed difference. I have used Atmega8s and Atmega168s in the same socket with the same circuitry and have never seen speed differences when executing identical programs, some of which do nothing but record the time, iterate through thousands of loops, and then record the time again.
Of course, if you have the fuse settings set wrong, it's possible to, say, have the Atmega168 cranking along at only 1MHz, but in those cases its serial port will not work with the default settings for the Arduino IDE and you'd have an objective sense of the problem instead of the subjective one you describe.