CPU speed is definitely one of the primary variables in dedupe speed. Disk speed is another - we've got some internal testing that has been done with RAID-5 volumes vs. RAID-1 that shows the lower write performance of the raid 5 volumes as compared to the raid 1 volume. But on some reasonably good hardware in house we've seen in the 3000 - 6000 MB/min range as well.
I'm glad you noted that the 1st backup of any resource is likely to be the slowest backup. Backups will generally get faster with time as the deduplication database grows with known deduplication fingerprints. The more fingerprints that exist in the deduplication database, the higher probability for a match, and thus, faster backups.
With regards to client vs. media server deduplication, Trimble, you are correct, in a small environment, it's very likely they will perform identically. However, as the number of concurrent backups increases, it's very likley that client deduplication will give better performance in the long run. There is a good perforamnce case to be made with client dedupe "spreading the load" of deduplication processing out to all the remote clients, rather than forcing the media server to handle all the dedupe processing load by itself.
Aidan Finley
Sr. Product Manager, Backup Exec